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: