Merge Sort - program in C, and how it works

Merge sort is one of the fastest sorting algorithms. As far as I've tested, the merge sort algorithm is only slightly slower than Quick sort.

The below program shows you how to implement the algorithm using the C programming language.

Merge Sort Program in C

#include <stdio.h>

void printArray(int numbers[], int n) {
    int i;
    for(i=0; i<n; i++) {
        printf("%d ", numbers[i]);
    }
    printf("\n");   
}

void merge (int arr[], int leftIndex, int middleIndex, int rightIndex) {
    /**
     * This function merges two sorted portions of an array,
     * into one sorted portion
     */
    int i,j,k,n1,n2;
    n1 = middleIndex-leftIndex+1;
    n2 = rightIndex-middleIndex;
    int L[n1], R[n2];
    for(i=0; i<n1; i++) {
        L[i] = arr[leftIndex+i];
    }
    for (j=0; j<n2; j++) {
        R[j] = arr[middleIndex+1+j];
    }

    i=0;
    j=0;
    k=leftIndex;

    while(i<n1 && j<n2) {
        if(L[i] < R[j]) {
            arr[k] = L[i];
            i++;
        }
        else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    while (i<n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    while (j<n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(int arr[], int leftIndex, int rightIndex) {

    /**
     * An array with one item => leftIndex = rightIndex, is already sorted,
     * that's how it starts working
     */

    if(leftIndex < rightIndex) {
        int middleIndex = leftIndex + (rightIndex - leftIndex) / 2;

        /**
         * recursively split the array,
         * until it cannot be split anymore
         */

        mergeSort(arr, leftIndex, middleIndex);
        mergeSort(arr, middleIndex + 1, rightIndex);

        /**
         * once splitting is done,
         * merge the parts together,
         * while sorting
         */
        merge(arr, leftIndex, middleIndex, rightIndex);
    }
}

int main() {
    int arr[] = {333, 468, 9738, 250, 9726, 17, 560, 4735, 3276, 325};
    int length;   
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Size of the array is %d\n", n);
    printf("Here is the array before sorting:\n");
    printArray(arr, n);

    mergeSort(arr, 0, n-1);

    printf("Here is the sorted array:\n");
    printArray(arr, n);
    return 0;
}

How it works

The array arr[] is predefined with ten values, it's the array we need to sort. The function mergeSort() receives the array, the left index, and the right index.

The function mergeSort() recursively splits the array at the middle index, until there is only element remaining in the array. It can't be split again, and need not be, because an array with one element is already sorted.

The function calls itself (recursion) for both the left side, and the right side. Once the splitting is finished, the recursion starts coming out and the merging starts.

Since both the arrays to merge are already sorted, merging is easy. This is what the function merge() does. It keeps comparing the lowest of left array to the lowest of the right array. Since it is sorted, lowest will always be on the left side of the corresponding array. So we can just keep incrementing the pointers i or j accordingly to compare the lowest elements. Whichever is smaller gets stored into the original array arr[] at the correct index.

When one of the array is exhausted, the remaining items are copied in the same order to the result array to complete the process.