Merge Sort

ull 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

oal 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

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



Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store