Merge Sort Algorithm

Hello people…! In this post I will talk about another sorting algorithm, the Merge Sort Algorithm, which is considered to be the fastest sorting technique by many. Merge Sort was invented by a famous computer scientist John von Neumann. It is a stable sort, so the relative position of the elements are preserved. It uses O(n) auxiliary memory to sort the elements in O(N log N) time. It is the classic example of Divide-and-Conquer Algorithms. It is very easy to understand and code. So, let’s get started..!

In the Merge Sort, we divide the array into halves recursively until we cannot divide further. Then, we merge them into a single array which would be sorted. The partitioning is similar to that in Quick Sort. We can put the merge part of the algorithm in a step-by-step process –

• Create an array which is large enough to accommodate all the elements of the two arrays to be merged.
• Compare the first elements of both arrays. Pick the least one and put it into the array we just created.
• Now we compare the first element of one array and the second element of the other array (from which the element was picked). We choose the smaller element and put it into the large array.
• We do this until we run out of elements. Then, our larger array is sorted.

For a better understanding of the merge procedure, look at the sketch below –

This is the way we merge two arrays. As you can see the prerequisite for this procedure to work is that the two smaller arrays that we are given must be sorted. How do we ensure this in our algorithm. Remember, at the lowest level, the partitions stop when the array has only one element, which is considered to be sorted. Then, we would merge two arrays of size 1 into a sorted array of size 2. This helps in merging two arrays of size 2 to form an array of size 4. In this way the recursion goes. So we will have the smaller arrays sorted initially.

As we have gained the knowledge about the working of the algorithm. Let’s put it in terms of pseudo-code. It comprises of two functions –

The pseudo-code is clear and self-explanatory. If you have any doubts, feel free to comment them. Looking at the pseudo-code try to code Merge Sort algorithm. If you get any doubts, keep reading the explanation again and again. I’m sure you’ll get it if you give your best. If you didn’t, don’t fret, I posted my code below –

I hope you get the intuition behind the Merge Sort Algorithm. It is the best example to explain Divide-and-Conquer technique. It has a runtime complexity of O(N log N). Which can be proved easily by using a Recursion Tree –

Optimisation – Merge Sort can be optimised to perform better. The idea behind this is the asymptotic complexities of various sorting algorithms. When we say that Merge Sort is better than Insertion Sort because it has a better worst case of O(n log n) which is less than O(n²), this is difference can be seen only for large values of ‘n’. This is because, the terms like O(n log n), O(n) and all are valid only when n → ∞ . So, for small values of ‘n’, like 100, we may not find any significant performance differences between Merge Sort and Insertion Sort. For smaller ‘n’ an optimised Bubble Sort can actually out perform the Merge Sort, because Merge Sort comes with a lot of overheads, the partition, the merging, the recursive calls and so. Whereas, the Bubble Sort has no such over heads. So, how about we apply an optimised Bubble Sort for smaller sized partitions inside the algorithm of Merge Sort…? That is how we optimise the Merge Sort.

But how do we decide how long this “smaller sized partitions” should be..? One way is you could do an analysis. You can just test your optimised Merge Sort for various lengths of cut-off’s. You need to run your code for the same input and keep varying the ‘threshold’ value below which the smaller sized partitions are sorted by optimised Bubble Sort and not by Merge Sort partitions. You could actually plot a graph between threshold and runtime, where you will find a minimum runtime for a certain value of threshold. But remember, if you want to see significant results you need to input as many as 10⁵ or 10⁶ values.

The next best thing you can do is make a guess by looking at your resources. The idea is to look at your cache. Let’s say your cache is 2MB. Then, your cache can accommodate an integer array of size 5 ✗ 10⁵. But, the whole of cache will not be available to you, so let’s say when you operate on an array of size 100, it is most likely that it’ll end up being in the cache. So, if we do an optimised Bubble Sort for arrays of size 100, we are most likely doing that in cache and as our process has less overheads, it actually increases the performance.

Its okay if your don’t get the whole threshold concept. But the gist of the discussion is that we will use an optimised Bubble Sort for smaller sized partitions in Merge Sort. Try to code this weird practice. You only have to make minor adjustments to your code. I’m sure you’ll get it if you give a little serious thought. I will post the code very shortly, until then keep trying!

This is the Merge Sort Algorithm. If you have any doubts or anything to say, feel free to comment them. I hope my post helped you in getting an idea of the Merge Sort. If it did, let me know by commenting…! Keep practising… Happy Coding…! 🙂