Merge Sort
2 min readMay 7, 2020
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
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.
Resources : Algorithms Robert Sedgewick
