Merge sort algorithm

Merge Sort Algorithm

We can classify sorting algorithms based on their complexity, selection sort, bubble and insertion sort have complexity of O(n2) while heap sort, merge sort and quicksort (with some assumptions) have complexity of  O(nlogn) and count and Radix sorts are linear O(n) algorithms.
In this post I will be concentrating on one sorting algorithm that is merge sort.
Merge sort falls in divide and conquer class of algorithm where input space is divided into subproblems and these subproblems are then solved individually and combined together to give solution to the original problem. Below figure explains divide and conquer paradigm.
Divide and conquer
In merge sort, input space is divided into two subproblems till the time we achieve smallest sub-problem and then the smallest sub-problem is solved, that is sorted and then combined up till the point where all of the original input is sorted. Question arises is what is the smallest sub-problem?  Smallest sub-problem is the condition where input cannot be further divided. In case of an array of integers, this will be met when there is only one element in the array.
From the above explanation, it is clear that sub-problems are subjected to same processing which is done on original input. That rings bell for recursion. And the base condition to stop recursion is derived in above paragraph, which is there is only one element in array.
Now, how do we combine two sub-problems solutions? This step is conquer part. Sort the smallest parts and combine them together with merge operation. In merge operation, we scan both sorted arrays and based on the comparison, put one of the two items into output array, till both arrays are scanned. If one array is finished before other, just copy all elements from the other array to output array. Copy this output array back to original input array so that it can be combined with bigger sub problems till solution to original problem is derived.
If don’t want to read, watch merge sort video


Below figure shows the merge sort operation.
merge step of merge sort
Let’s take and example and work out merge sort and then we will implement it.
Divide step
Divide step of merge sort
Conquer step
Conquer step of merge sort
Merge sort implementation
Code explanation
For mergesort function we get three parameters, the input array a[], the start index and the end index of array. This start and end change in every recursive invocation of mergesort function.
We find the middle index using start and end index of the input array and again invoke the same function with two parts one starting from start to mid and other being from mid+1 to end.
Once base condition is hit, we start winding up and call merge function. Merge function takes four parameters, input array, start, end and middle index based on start and end.
Merge function merges two sub arrays (one from start to mid and other from mid+1 to end) into a single array from start to end. This array is then returned to upper calling function which then again sort two parts of array.
Complexity analysis
As we know that every time input space is divided into two and from the binary search algorithm we know that this division will have complexity of O(log n) where n is input size. So the first part of implementation of merge sort has complexity of O(logn). Now the second part of implements merge step which place every elements in its proper place in array, hence it linear time O(n). Since above step of dividing has to be done for n elements, hence total complexity of merge sort will be O(nlogn).
However, there is one caveat, every time we merge, two subarrays an auxiliary array is needed to temporarily store array elements and that incurs O(n) space complexity on merge sort algorithm.

There are some improvements which can be done on this algorithm.
1. When number of elements are less than some threshold, one can use insertion or selection sort to sort those numbers.  Why? Because when n is small, O(n2) is as good as O(nlogn) and it saves extra overhead of split and merging. All in all, using insertion sort in input array with small size, can give better performance.

2. Before calling merging, check if all the elements in right array are greater then left array, if yes, no need of merging. This can be easily checked by comparing a[mid] with a[mid+1]. If a[mid] is less than a[mid+1],  two sub arrays are already sorted and we don’t need to perform merge.

External Merge sort

Merge sort is best used when data is in huge in size as compared to available memory, like sorting 2GB of data when we have only 100 MB of RAM or physical memory. Data cannot fit in memory and resides on to disk from where it is fetched in chunks and merged.
There are two passes in the external merge sort : Sort pass and merge pass. below figure explains this

external merge sort

Sort pass

  • Divide the input in N chunks where N  = Size of total data/Size of available memory
  • Load each chunk in main memory and sort it with any conventional sorting algorithm.
  • Now load a predefined block of the sorted chunks into memory again. keep a buffer to store sorted output.

Merge Pass

  • Now have N-way merge and put output on to buffer. As buffer get full, write that onto disk.
  • If any of the small chunk taken if exhausted, one can fill the next block from the same chunk.

External merge sort can be improved significantly using parallelism where data chunks are written on different disk where read and write can be performed in parallel. Also, different chunk can be sorted on different processors in parallel. If processors are not available, merge routine can take advantage of multithreading.
There is one problem which is classic example of usage of external merge sort is mentioned here in problem number 5 and solved here : External merge sort.

If you have any other optimization trick or better way to implement merge sort please comment below.