MergeSort with practical improvement

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:


Enhanced by Zemanta