Understanding the Recursion of mergesort

2c2c picture 2c2c · Sep 28, 2013 · Viewed 42.5k times · Source

Most of the mergesort implementations I see are similar to this. intro to algorithms book along with online implentations I search for. My recursion chops don't go much further than messing with Fibonacci generation (which was simple enough) so maybe it's the multiple recursions blowing my mind, but I can't even step through the code and understand whats going on even before I even hit the merge function.

How is it stepping through this? Is there some strategy or reading I should undergo to better understand the process here?

void mergesort(int *a, int*b, int low, int high)
{
    int pivot;
    if(low<high)
    {
        pivot=(low+high)/2;
        mergesort(a,b,low,pivot);
        mergesort(a,b,pivot+1,high);
        merge(a,b,low,pivot,high);
    }
}

and the merge(although frankly I'm mentally stuck before I even get to this part)

void merge(int *a, int *b, int low, int pivot, int high)
{
    int h,i,j,k;
    h=low;
    i=low;
    j=pivot+1;

    while((h<=pivot)&&(j<=high))
    {
        if(a[h]<=a[j])
        {
            b[i]=a[h];
            h++;
        }
        else
        {
            b[i]=a[j];
            j++;
        }
        i++;
    }
    if(h>pivot)
    {
        for(k=j; k<=high; k++)
        {
            b[i]=a[k];
            i++;
        }
    }
    else
    {
        for(k=h; k<=pivot; k++)
        {
            b[i]=a[k];
            i++;
        }
    }
    for(k=low; k<=high; k++) a[k]=b[k];
}

Answer

abe312 picture abe312 · Dec 11, 2015

MERGE SORT:

1) Split the array in half
2) Sort the left half
3) Sort the right half
4) Merge the two halves together

enter image description here

enter image description here