https://www.toptal.com/developers/sorting-algorithms

Full scientific understanding of their properties has enabled us to develop them in practical system sort and Quick-sort honored as one of top 10 of 20th century in science and engineering

Basic Plan of merge-sort

  • Divide array into two halves
  • Recursively sort each half
  • Merge two halves
http://sorting.at/

Goal of this story is given two sorted sub-arrays a[lo] to a[mid] and a[mid+1] to a[hi], replace with sorted sub-array a[lo] to a[hi]

Merge-sort uses at most NLogN compares and 6NLogN array access to sort any array of size N
for improvements we can use insertion-sort (N²)for small sub-arrays, because merge-sort has too much overhead for tiny sub-arrays

Practical Improvment

  • Stop if already sorted, if biggest item in first half ≤ smallest item in second half?

and instead of recursion for figure-out complexity we can use Bottom-up merge-sort

To access to completed source, please check Room Project on this link.

I have a dream to have a spectacular garden