Merge Sort

Merge-sort is an application of Divide and Conquer paradigm. To read more about Divide and Conquer, follow this post. 

In merge-sort we follow following steps:
1. Divide the original array of size n into 2 halves of size n/2 each
2. Sort the two halves individually.
3. Merge the two sorted halves to get a sorted array of original size.

Following is the C++ implementation of merge sort , for an unsorted array of integers : {6, 2, 8, 12, 10, 9, 50, 24, 3, 1}


#include <iostream>
using namespace std;

#define MAX_NUM 100

// Auxiliary function to merge 2 sorted sub-arrays and produce a sorted array
void merge(int arr1[], int low, int pivot, int high)
{
    int arr2[MAX_NUM];

    cout << "Merging arrays : [ " ;
    for(int x=low; x<=pivot; x++)
        cout << arr1[x] << " ";
    cout << "] and [ ";
    for(int x=pivot+1; x<=high; x++)
        cout << arr1[x] << " ";
    cout << "]" << endl;

    int count = high-low;

    int mid = pivot+1;
    int i = low;
    while(low <= pivot && mid <= high)
    {
        if(arr1[low] <= arr1[mid])
            arr2[i++] = arr1[low++];
        else
            arr2[i++] = arr1[mid++];
    }
    while(mid <= high)
        arr2[i++] = arr1[mid++];

    while(low <= pivot)
        arr2[i++] = arr1[low++];

    cout << "Merged Array: [ ";

    // Copy sorted values from arr2 to original array arr1
    for(int x=0; x<=count; x++)
    {
        cout << arr2[high-count+x] << "  ";
        arr1[high-count+x] = arr2[high-count+x];
    }
    cout << "]" << endl;
}

// Main mergeSort function
void mergeSort(int arr1[], int low, int high)
{
    cout << "Merge sort called on array : [ " ;
    for(int x=low; x<=high; x++)
        cout << arr1[x] << " ";
    cout << "]" << endl;

    if(low < high)
    {
        int mid = (high+low)/2;
        mergeSort(arr1, low, mid);
        mergeSort(arr1, mid+1, high);
        merge(arr1, low, mid, high);
    }
}

// an auxiliary function to print the contents of an array
void printArray(int arr[], int n){
    cout << "{ ";
    for(int i=0; i<n; i++)
        cout << arr[i] << "  ";
    cout << "}" << endl;
}

int main(int argc, char* argv[])
{
    int A[10] = {6, 2, 8, 12, 10, 9, 50, 24, 3, 1};
    cout << "Original Array : ";    printArray(A, 10);

    mergeSort(A, 0, 9);
    cout << "Sorted Array : ";    printArray(A, 10);

    return 0;
}

Output :

Original Array : { 6  2  8  12  10  9  50  24  3  1  }
Merge sort called on array : [ 6 2 8 12 10 9 50 24 3 1 ]
Merge sort called on array : [ 6 2 8 12 10 ]
Merge sort called on array : [ 6 2 8 ]
Merge sort called on array : [ 6 2 ]
Merge sort called on array : [ 6 ]
Merge sort called on array : [ 2 ]
Merging arrays : [ 6 ] and [ 2 ]
Merged Array: [ 2  6  ]
Merge sort called on array : [ 8 ]
Merging arrays : [ 2 6 ] and [ 8 ]
Merged Array: [ 2  6  8  ]
Merge sort called on array : [ 12 10 ]
Merge sort called on array : [ 12 ]
Merge sort called on array : [ 10 ]
Merging arrays : [ 12 ] and [ 10 ]
Merged Array: [ 10  12  ]
Merging arrays : [ 2 6 8 ] and [ 10 12 ]
Merged Array: [ 2  6  8  10  12  ]
Merge sort called on array : [ 9 50 24 3 1 ]
Merge sort called on array : [ 9 50 24 ]
Merge sort called on array : [ 9 50 ]
Merge sort called on array : [ 9 ]
Merge sort called on array : [ 50 ]
Merging arrays : [ 9 ] and [ 50 ]
Merged Array: [ 9  50  ]
Merge sort called on array : [ 24 ]
Merging arrays : [ 9 50 ] and [ 24 ]
Merged Array: [ 9  24  50  ]
Merge sort called on array : [ 3 1 ]
Merge sort called on array : [ 3 ]
Merge sort called on array : [ 1 ]
Merging arrays : [ 3 ] and [ 1 ]
Merged Array: [ 1  3  ]
Merging arrays : [ 9 24 50 ] and [ 1 3 ]
Merged Array: [ 1  3  9  24  50  ]
Merging arrays : [ 2 6 8 10 12 ] and [ 1 3 9 24 50 ]
Merged Array: [ 1  2  3  6  8  9  10  12  24  50  ]
Sorted Array : { 1  2  3  6  8  9  10  12  24  50  }