C programming concepts: Merge Sort

Algorithm

Merge sort uses a divide and conquer approach.

Divide the array repeatedly into 2 subarrays until a single element is left(Single element is already sorted).

Merge 2 sorted subarrays in a single sorted array.

Example

Let Array = 6 5 3 1 8 7 2 4

Divide : Trace the black bordered array
Merge : Trace the blue bordered array

Code

divide function : Recursively calls divide on the 2 divided subarrays.

merge function : Merges the 2 subarrays into a sorted array.

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

void merge(int a[],int low,int mid,int high)
{
    int temp[30];                         //temporarily store sorted elements 

    int i = low,j = mid+1;                //start index of subarrays
    int k = low;

    while(i<=mid && j<=high)             //mid = end index of 1st subarray,high = end index of 2nd subarray
    {
        if(a[i]>a[j])
            temp[k++]=a[j++];
        else
            temp[k++]=a[i++];
    }

    while(i<=mid)                        //copy remaining elements of 1st subarr
        temp[k++]=a[i++];

    while(j<=high)                      //copy remaining elements of 2nd subarr
        temp[k++]=a[j++];

    for(k=low;k<=high;k++)             //copy from temp[] to a[]       
        a[k] = temp[k];
}

Code Tracing

Lets trace mergesort code for clear understanding using a call stack.

When a function invokes,its activation record is pushed on the call stack and when it finishes execution,its activation record is popped off from the call stack.Activation record comprises of many things but I am just showing the things that help understand recursion.Below I trace the divide and merge functions.

Divide function