Merge Sort
Everybody has their favorite algorithms, and Merge sort happens to be one of mine. It’s the definitive “Divide and Conquer” Algorithm. There is a certain elegance to Merge sort, and unlike Quicksort, it is a stable sorting algorithm, meaning that when sorting records, the order of records with identical keys is preserved. The one downside to Merge sort is that it requires O(n) additional space as it is not an in-place sort, so if your using Merge sort to sort an array of objects, you may want to sort an array of pointers to objects instead of sorting the objects themselves, thus reducing the memory overhead.
There are two fundamentally different approaches to implementing merge sort: Top Down Merge sort which is a recursive divide and conquer algorithm, and Bottom Up Merge sort which is an iterative dynamic programming algorithm. I’m going to explain the Top down approach as its far and away the more common approach, and illustrates the way the algorithm works a more comprehendible fashion.
How it works
As stated above Merge sort is a divide and conquer algorithm. It works by recursively halving the input array into smaller and smaller pieces until it is comprised of singlets, as a single item is itsself sorted. There are two approaches to mergesort, the naiive approach, and the implicit approach.
Pseudocode for the naiive approach looks like this:
mergesort(array): let front be an array let back be an array let result be an array if (array.length <= 1) return for (i = 0 to array.length/2) copy(array[i] to front[i]) for (j = array.length/2 to array.length) copy(array[j] to back[j]) mergesort(front) mergesort(back) merge(front, back, result) return result
Pseudocode for the implicit merge sort algorithm looks like this:
mergesort(array, left, right): if (right - left <= 1) return middle = right+left / 2 mergesort(array, left, middle) mergesort(array, middle, right) merge(array, workarray, left, middle, right)
The naiive approach proceeds by the actual splitting of the array into two other arrays, copying the values from the input array into two work arrays (front and back) and then in the merge function, copying the data from the two work arrays to the result array. While straight forward and illustrative of how the algorithm works, this approach is inefficient because the large amount of copying of data taking place.
The second method passes array boundaries as its parameter, leaving all data copying to be done in the merge phase, creating a far more efficient implementation. This is the method we will be using in this article.
The Sorting Phase (Divide)
The sorting phase of mergesort is a recursive function used to set the array boundary delimiters so the merge function knows which slices of the array to work on. It’s a pretty straight forward process that has a pretty much 1-to-1 translation of its pseudocode:
I should point out that the call to MergeSort is allocating a work array which is then passed as a value to the msort() function which is the function doing the actual work, the reason for this is that if we didn’t declare a work array here and pass it (by reference) to the future functions, we’d be left having to allocate an array every time the merge() function is called, which would incur a significant overhead and DRASTICALLY slow the algorithm down. Don’t believe me? try it both ways and time your results of each method, you might be pretty surprised at how much time allocating memory takes. While i haven’t done this test in Java, i have done it with C++ using both arrays and vectors, and both were SIGNIFICANTLY slower than pre-allocation, and if its slow in C++, it will be even slower in Java, thats just the way of things.
The Merge Phase (Conquer)
Merging is a fundamental concept not just to sorting, but to data processing in general, and there are many, many ways to write a merge function. In Robert Sedgewicks ‘Algorithms’ he demonstrates a pretty slick method of copying the first half backwards and the second half forwards and using each other as sentinels. While it’s a neat trick, it does not display a significant performance enhancement over the more straight forward approach i’m going to cover here.
Merging works like this: were passed pointers to the beginning, middle, and end of the list, represented as ‘l’, ‘m’, and ‘r’. the values from ‘l’ to m – 1, represent the ‘front’ half of the array and the values from ‘m’ to ‘r’ represent the ‘back’ half. We assign the value of ‘l’ to a counter ‘i’, and the value of ‘m’ to a counter ‘j’, we then compare the values of the array at position ‘i’ ver position ‘j’ and take which ever is smaller, incrememnting the appropriate counter. If one section runs out of values before the other, the rest of the other array is appended to the end of the work array.
Heres a working example in java:
With that we have a working mergesort. But i’d like to take a moment to point out a few improvements that can be made to improve running time and efficiency.
Optimizing Merge Sort
I seperated the recursive function and the merge operation into two seperate functions for the ease of explaining the two phases and illustrating its divide and conquer approach, however we can combine them into one function which will give us a slight speed increase, as well as aid in keeping the size of the call stack down (Remember that Mergesort is a Recursive algorithm). We can also borrow a page from Quicksorts book and set a thresh hold that switches merge sort to insertion sort when the array hits a certain size.
With these two modifications in place our final algorithm looks like this:
As i mentioned above, you can also implement a Bottom Up iterative form of this algorithm, which some evidence points to being slightly faster, while also not requiring the space on the call stack of the above recursive approach. Robert Sedgewicks book “Algorithms” covers this, and many other merge sort topics in some detail and is well worth a look.
A proper merge sort implementation is hard to beat in the speed department, And with the amount of resources available in modern development environments the O(n) space complexity is not as costly as it once was, especially when you factor in the reliable O(nlogn) computational complexity and inherent stability, not to mention merge sorts ability to digest huge lists without blinking an eye and its natural adaptability for external sorting. It’s no wonder that merge sort replaced quicksort as Perls standard sorting algorithm, as well as being used for the C++ standard libraries std::stable_sort. In head to head comparisons, using C++ my mergesort implementation consistently came out ahead of the STL’s Introsort algorithm (std::sort) and much faster than std::stable_sort.
