Expert: Narendra - 4/20/2006

Question
I'm not able to understand how the merge sort recursive function works, I've checked the text books but they don't give any specific examples. Can you please help me out! Thanks!

Example:  3  5  2  6  8

This is the function:

mergesort(int a[], int low, int high)
{
int mid;
if(low<high)
{
mid=(low+high)/2;
mergesort(a,low,mid);
mergesort(a,mid+1,high);
merge(a,low,high,mid);
}
return(0);
}

merge(int a[], int low, int high, int mid)
{
int i, j, k, c[50];
i=low;
j=mid+1;
k=low;
while((i<=mid)&&(j<=high))
{
if(a[i]<a[j])
{
c[k]=a[i];
k++;
i++;
}
else
{
c[k]=a[j];
k++;
j++;
}
}
while(i<=mid)
{
c[k]=a[i];
k++;
i++;
}
while(j<=high)
{
c[k]=a[j];
k++;
j++;
}
for(i=low;i<k;i++)
{
a[i]=c[i];
}
}

Answer
MergeSort uses divide & conquer strategy to sort the elements.
Here, you go on dividing till only one element is left.
Then this element will be merged with the next one and both will be put in correct order and since this is a recursive function, it will be repeated till you complete the merge and come out.

So, here is the sequence of calls:
a[] = {3, 5, 2, 6, 8}
low = 0; high = 4;
mergesort(a, 0, 4)
mid = 0 + 4 / 2 = 2
mergesort(a, 0, 2)
mergesort(a, 3, 4)
merge(a, 0, 4, 2)

So, each of the mergesort() calls will again go back and call mergesort() and merge(),
this goes on till: (low < high) is satisfied.

In the example you have taken there are only 5 elements and is very easy to simulate.
So, why don't you go on trying as I showed till it comes out and you will see a sorted list.
It is worth doing this excercise and in the end you will know how it works.