Pекурсивная версия функции merge

[stasito]

дан код программы,
нужно переделать функцию merge в рекурсивную,
есть у кого-то идеи?


const int SIZE = 8;

//Merge is non-recursive function that takes two sorted lists that are placed
//inside a single array, the first one between indices left1-right1
// and the second between left2-right2 and make the entire array sorted
//The function uses a temporary array vtemp to store the results

void merge(int v[SIZE],int left1,int right1,int left2,int right2)
{
int vtemp[SIZE], i, nc, left, right;

left=left1;
right=right2;

nc=left;
while ((left1<=right1) && (left2<=right2))
{
if (v[left1]<v[left2])
{
vtemp[nc]=v[left1];
nc++;
left1++;
}
else
{
vtemp[nc]=v[left2];
nc++;
left2++;
}
}

//when one of the lists has been totally used, we just need
//to transfer elements from the other list
if ((left1>right1)||(left2>right2))
{
if (left1>right1)
while (left2<=right2)
{
vtemp[nc]=v[left2];
left2++;
nc++;
}
else
while (left1<=right1)
{
vtemp[nc]=v[left1];
left1++;
nc++;
}
}

for (i=left;i<=right;i++)
v[i]=vtemp[i];
}


//Recursive msort
void msort(int v[SIZE],int left,int right)
{
int right1,left1,right2,left2;
//Sort the elements between left..right
//Stop condition: enter only when there is still "space"
if (left<right)
{
left1=left;
right1=(right+left)/2;
left2=(right+left)/2+1;
right2=right;

//recursivly sort the left side
msort(v,left1,right1);

//recursivly sort the right side
msort(v,left2,right2);

//merge the two lists
merge(v,left1,right1,left2,right2);
}
}


//main program
void main()
{
int v[SIZE], i;

for (i=0;i<SIZE;i++)
{
cout<<"enter a number \n";
cin>>v[i];
}

msort(v,0,SIZE-1);

for (i=0;i<SIZE;i++)
cout<<"The "<<i<<" element is "<<" "<<v[i]<<"\n";
}