Well MergeSort is a non-trivial sorting algorithm with time complexity O(NlogN) and space complexity O(N). It has very simple concept with both top-down and bottom-up approaches.
There are some practical improvements according to the book Algorithms, 4th Edition from Princeton University.
- Overhead for sorting small arrays: for array with size less than a CUTOFF value (it is set to 7), use insertion sort instead.
- Before merging: if the largest value of the left sorted half is less than the smallest value of the right sorted half, there is no need for merging.
- can’t remember…
The improved code is on github:
The bottom-up version: