Merge Sort was invented by John von Neumann in 1945, and is an algorithm belonging to the “divide and conquer” class of algorithms. Meaning, the algorithm splits an input into various pieces, sorts them and then merges them back together.
Runtime of Merge Sort
If we rephrase this algorithm:
- Divide the array into various “chunk” to process
- Merge the array while sorting (conquer)
Below I’ll provide a very basic example:
Input: {4, 1, 5, 8, 9, 3, 2, 6, 7}
Divide: {4, 1, 5, 8}, {9, 3, 2, 6, 7}
Divide: {4, 1}, {5, 8}, {9, 3}, {2, 6}, {7}
Divide: {4}, {1}, {5}, {8}, {9}, {3}, {2}, {6}, {7}
Merge: {1, 4}, {5, 8}, {3, 9}, {2, 6}, {7}
Merge: {1, 4, 5, 8}, {2, 3, 6, 9}, {7}
Merge: {1, 2, 3, 4, 5, 6, 8, 9}, {7}
Merge: {1, 2, 3, 4, 5, 6, 7 ,8, 9}
In the above, you can see that I bold when we alter the position of a variable. It is clear that by dividing first it is easier to merge in order because we have to change positions less often, than say brute forcing. Brute forcing would be much slower because we would in the worst case have to search though the whole array each time and copy/move each value into a new array/flip positions. Thereby giving a brute force sorting algorithm a runtime of O(n^2).
Merge sort on the other hand is significantly quicker at sorting and further, can actually be implemented (more easily) in parallel (across multiple CPUs). Merge Sort in big-o notation, where n is the size of the array, as the following:
- Runtime: O(nlogn)
- Memory: O(n)
Implementing Merge Sort in Go
Merge Sort is a fairly quick algorithm and can often be implemented in parallel, however I chose to not implement a parallelized version in Go[1]. That being said, implementing the algorithm is really straight forward.
First, the input array needs to be divided into chucks to be sorted. This can be achieved in Go by finding the middle of the array (or slice in Go), and taking a slice from the left and a slice from the right and recursively call MergeSort(array) until there is only one node in the array.
As you can see, I recursively call Mergeort(slice[:mid]) and mergeSort(slice[mid:]), which represent the left and right portions of the array, or slice in the case of Go. To merge, we must also sort, to do this we make a new slice (also avoiding destroying the original, unsorted slice). We then keep track of the left and right slices to be merged and just pick the next smallest value from the left or right slice to add to our new slice. Think of it as picking the next best value from two piles, all the way down, until you have only one pile.
The output of each sorted slice feeding into the next recurrence, with the final, sorted slice, being returned to the main loop.
An example run of the program:
— unsorted —
[56843 -76716 -42042 30846 50290 -27458 47259 91477 6775 59768 15476 -21788 -33386 42947 -27244 -45848 -7689 14298 -41118 -99082 -3641 -27944 -59233 25235 -44990 56287 -13288 8899 2579 -28954 27772 41360 34462 8174 53027 -22394 -91773 -42887 14202 30264 42811 -43774 -3273 11149 27266 -32695 31350 -5934 30010 -32840]
— sorted —
[-99082 -91773 -76716 -59233 -45848 -44990 -43774 -42887 -42042 -41118 -33386 -32840 -32695 -28954 -27944 -27458 -27244 -22394 -21788 -13288 -7689 -5934 -3641 -3273 2579 6775 8174 8899 11149 14202 14298 15476 25235 27266 27772 30010 30264 30846 31350 34462 41360 42811 42947 47259 50290 53027 56287 56843 59768 91477]
That’s it!
The full program is available on my Github.