Merge sort explained with simple example

Merge sort is one of the simplest sorting algorithm, which works on Divide and Conquer algorithm. In this sorting algorithm, input data is divided into two halves/sublist which then acts as input data and furthur divided into two halves so that finally every sublist contains a single element. Finally, these sublists are merged in sorted order which results into sorted data.

Pros:
1) Simple algorithm and hence efficient for small list of data.
2) Good for sorting data represented in Linked list.
3) This algorithm is stable (performance is equal in all cases) and insensitive to the distribution of initial data.

Cons:
1) Extra space needed in O(n).

Algorithm explained via example:

Let us take an example array “7 9 3 12 1”. Now we will run through this array with merge sort algorithm to understand how it works.

First division (divide the list into two halves):
{7, 9, 3} and {12, 1}, After dividing the list into two halves

Second division (divide the sub-list into two halves):
{7, 9}, {3}, {12} and {1}, After dividing the list into two halves

Third division (divide the sub-list into two halves):
{7}, {9}, {3}, {12} and {1}, After dividing the list into two halves

At this point we have got sublists with single element each.
Now, we will start merging these sub-lists in sorted order to get bigger sorted sub-lists

First merge (merge the sub-list in ascending order)
{7, 9}, {3, 12} and {1}

Second merge(merge the sub-lists in asecnding order)
{3, 7, 9, 12} and {1}

Finally merge the last sub-lists
{1, 3, 7, 9, 12}

Now the list is sorted.

Let’s have a look at the sample program for Merge sort.

void printArray(int a[] )
{
    for (int i = 0; i < 12; i++)
    {
        cout << a[i] << ", ";
    }
    cout << endl;
}
// This function will merge the sub-lists to create bigger list in sorted order
void merge(int array[], int startIndex, int mid, int endIndex)
{
    int i = startIndex;
    int j = 0;

    // Temp array 
    int a[6], b[6];

    // Copying 1st array elements
    for (; i <= mid; i++)
    {
        a[j] = array[i];
        j++;
    }

    // Copying 2nd array elements
    i = mid + 1;
    j = 0;
    for (; i <= endIndex; i++)
    {
        b[j] = array[i];
        j++;
    }

    int len1 = mid - startIndex + 1;
    int len2 = endIndex - mid;

    i = 0; 
    j = 0;

    // Merging both list 
    while (i < len1 && j < len2)
    {
        if (a[i] < b[j])
        {
            array[startIndex] = a[i];
            i++;
        }
        else
        {
            array[startIndex] = b[j];
            j++;
        }
        startIndex++;
    }

    // Adding remaining item of list 1 in main array
    while (i < len1)
    {
        array[startIndex] = a[i];
        i++;
        startIndex++;
    }

    // Adding remaining item of list 2 in main array
    while (j < len2)
    {
        array[startIndex] = b[j];
        j++;
        startIndex++;
    }
}
// This function will divide the input list into small list
void split(int array[], int startIndex, int endIndex)
{
	if (startIndex == endIndex)
		return;

	int mid = (startIndex + endIndex) / 2;

	split(array, startIndex, mid);
	split(array, mid + 1, endIndex);

	merge(array, startIndex, mid, endIndex);
}

void mergeSort()
{
    int a[] = { 76,4,65,33,23,10,44,38,97,100,1,59 };
    cout << "Merge Sort" << endl;
    cout << "Initial array" << endl;
    printArray(a);

    split(a, 0, 11);
    printArray(a);
}

int main()
{
    mergeSort();
}

Output of the above program is as follows:

Merge Sort
Initial array
76, 4, 65, 33, 23, 10, 44, 38, 97, 100, 1, 59,
1, 4, 10, 23, 33, 38, 44, 59, 65, 76, 97, 100,

Algorithm performance:

Time complexity:
Merge sort is not affected by data distribution.Time complexity for best and worst both case scenario is O(nlogn).

Space complexity:
Since, extra space is needed for this sorting algorithm. Hence, Space complexity is O(n).