Merge Sort

Merge sort is a "Divide and Conquer" algorithm which divides input array into two halves, calls itself for the two halves and then merges the two sorted halves. Basically, merge sort merges two sorted sub-arrays into one sorted array. For example: Let array A[] = {4, 5, 8, 9} and array B[] = {1, 2, 6, 10}, then the resulting array C[] = {1, 2, 4, 5, 6, 8, 9, 10}.

Merge sort is shown below for merging two separate sorted arrays into one sorted array, and then for merge-sorting a given unsorted array with help of recursion.

1. Merging two sorted arrays into one sorted array:
The idea is to place index variables i and j at start of the two arrays A[] and B[] respectively. Now compare the corresponding elements of the two arrays, copy the smaller element into the result array C[] and increment that index. Also, when one of the arrays is completely exhausted, just copy the remaining elements from the other array into the result.

void mergeSort(int *A, int *B, int *C, int sizeA, int sizeB, int sizeC)
{
    int a = 0, b = 0, c = 0;
    
    while(c < sizeC)
    {   
        if(a >= sizeA)          C[c++] = B[b++];    // Array A[] was exhausted
        else if(b >= sizeB)     C[c++] = A[a++];    // Array B[] was exhausted
        else if(A[a] < B[b])    C[c++] = A[a++];
        else                    C[c++] = B[b++];
    }
}

2. Merge sort a given array with help of recursion:
Now we know that we need two sorted arrays and we can merge sort them. Given an unsorted array, we can keep on splitting the array into two halved (sub-arrays) until size of sub-arrays reaches one. Now we can merge sort the sub arrays back to the actual array of given size, but in sorted order. The function mergeSortRecursive() is used to part the array into sub-arrays recursively until single elements are reached. The merge() function is used for merging two halves. This function merge(A, left, mid, right) assumes that sub-arrays A[left..mid] and A[mid+1..right] are sorted and merges the two sorted sub-arrays into one.

Time complexity: O(n log n)
Space complexity: O(n) (For taking an auxiliary array.)

#include <stdio.h>

void merge(int *A, int left, int mid, int right)    // For merge-sorting the array partitions A[left to mid] and A[mid+1 to right]
{
    int B[right];
    int i = left, j = mid+1, k;

    for(k = left; k <= right; k++)
    {
        if(i > mid)               B[k] = A[j++];    // Left array was exhausted. Copy right sub-array directly
        else if(j > right)        B[k] = A[i++];    // Right array was exhausted. Copy left sub-array directly
        else if(A[i] < A[j])      B[k] = A[i++];
        else                      B[k] = A[j++];
    }

    for(k = left; k <= right; k++)
        A[k] = B[k];
}

void mergeSortRecursive(int *A, int left, int right)    // For partitioning array recursively [in O(log n)] and then merge-sorting the 2 parts [in O(n)] via merge() function
{
    int mid;

    if(left < right)
    {
        mid = (left + right) / 2;
        mergeSortRecursive(A, left, mid);       // Partition
        mergeSortRecursive(A, mid+1, right);    // Partition

        merge(A, left, mid, right);             // Merge sort
    }
}

int main()
{
    int i, size;
    printf("\n\nEnter size of array: ");
    scanf("%d", &size);
    int A[size];

    printf("\n\nEnter %d elements: \n", size);
    for(i = 0; i < size; i++)
        scanf("%d", &A[i]);

    mergeSortRecursive(A, 0, size-1);

    printf("\n\nMerge sorted: ");
    for(i = 0; i < size; i++)
        printf(" %d ", A[i]);

    return 0;
}

Here is a diagram that tries to explain what is happening in recursive merge sort (taken from Wikipedia):