Simplifying Merge Sort

In this article I’ll be trying (really hard !! ) to explain in a simple manner a really famous sorting Algorithm Drrrrrrrrrrrrrrrrrum-roll MERGE SORT. I have tried to keep it as simple as possible, without getting into technical details to help you understand the logic behind the algorithm.

What is Merge Sort ?

Merge Sort is a really cool sorting algorithm that uses the concept of divide and conquer to sort the given data in order of O(n*log n) in all the three cases, best average and worst. For those not familiar with the concept of time complexity, just understand its a really efficient algorithm ( and when are you planning on studying time complexity huh? ).

For my nerdy friends here’s a proper definition from the internet : In computer science, merge sort is an efficient, general-purpose, comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the order of equal elements is the same in the input and output. Merge sort is a divide and conquer algorithm that was invented by John von Neumann in 1945

How does it work ?

Before going to the generic tree like diagram I would like you to look at the code, just look at it, don’t try to make sense out of it. Just look and see that in the function mergeSort the only part where some real work is being done is the merge function, rest is recursively calling the mergeSort function. So if one understands the merge function well, rest shouldn’t be a problem. (Warning you again : don’t be tempted to make sense out of it yet just look and scroll !!)

void mergeSort(int arr[],int l,int r){
if(l>=r){
return;//returns recursively
}
int m =l+ (r-l)/2;
mergeSort(arr,l,m);
mergeSort(arr,m+1,r);
merge(arr,l,m,r);
}
void merge(int arr[], int l, int m, int r)
{
// DONT WORRY ABOUT THE IMPLEMENTATION JUST SCROLL 
int n1 = m - l + 1;
int n2 = r - m;
// Create temp arrays
int L[n1], R[n2];
// Copy data to temp arrays L[] and R[]
for (int i = 0; i < n1; i++)
L[i] = arr[l + i];
for (int j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
// Merge the temp arrays back into arr[l..r]
// Initial index of first subarray
int i = 0;
// Initial index of second subarray
int j = 0;
// Initial index of merged subarray
int k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
}
else {
arr[k] = R[j];
j++;
}
k++;
}
// Copy the remaining elements of
// L[], if there are any
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
// Copy the remaining elements of
// R[], if there are any
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}

The Merge Function

Now that you would have been scandalised by the length of the merge function, let us see how simple it is.

What the merge function does is simply takes two individually sorted arrays and merges them to make one single sorted array. That’s it !! The picture given below explains how two arrays are merged.

(source : https://javabypatel.blogspot.com)

Now that the merge function is clear ( at-least I assume so, if not go through the photo again), let us move forward.

With the knowledge so far we can make one sorted array from two individually sorted arrays, and this knowledge feels useless as we are not given two sorted arrays but a single unsorted array.

How to use the merge function to solve our problem ?

What we can do is we can divide the array into parts that are individually sorted. For example :

[2,4,7,1,5,9,11] is made up of two sorted arrays 
[2,4,7] and [1,5,9,11]

So we can merge and get a sorted array. But there is no guarantee that all arrays in the world will be made of two sorted arrays eg : [2,1,13,4,17,9,10] is not made of two sorted arrays

But there is a guarantee that a array of n elements will be make of n sorted arrays

[2,1,13,4,17,9,10] is made up of 7 sorted arrays 
[2] ,[1] ,[13] ,[4] ,[17], [9], [10]
because an array of single element will be sorted (silly & obvious fact)

So if we break the the array in such manner and then use the merge function to merge two arrays at a time like :

[2] ,[1] -> [1,2]
[13] ,[4] -> [4,13]
[17], [9] -> [17,9]
[10] -> [10] (leave it as it is and deal with it later)
And merge the new arrays again :
[1,2] , [4,13] -> [1,2,4,13]
[17,9] , [10] -> [9,10,17]
And again for the final time : 
[1,2,4,13] ,[9,10,17] -> [1,2,4,9,10,13,17]
Important : In reality the algorithms first breaks and merges left half and then the right half(video at the end gives a visual representation of the same), rather than breaking all the elements first and then merging like shown above, it was done to simplify the logic.
(for a better understating read about recursion and how call stack works and then go through the code)

And kaboom…We sorted the array !!

The picture below summaries the complete process. The red portion is breaking the array into half recursively so as to obtain individual elements and then green portion is merging the individual elements into sorted arrays taking two arrays at a time.

(Source : https://dotnettutorials.net)

A Visual Delight :

I would end with a really interesting video that shows how the Merge Sort algorithm works, do have a look :