Merge Sort

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.




I have a dream to have a spectacular garden

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Ansible Dynamic Inventory AWS

👉👉Best Way to learn programming👈👈

Discover hidden functions in your car (using CAN bus sniffing)

What is a DLL File?

Create AWS lambda using ReasonML and Bucklescript

.NET core Service lifetimes (AddTransient vs AddScoped vs AddSingle)

Unity Development — Collectables

{UPDATE} Farlige røvere og politi chase simulator - Dodge gennem motorvej trafik og arrestere…

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
Ahmad Berahman

Ahmad Berahman

I have a dream to have a spectacular garden

More from Medium

What is recursion and how to write it?

The most common coding interview questions (and how to answer them)

A very big sum | HackerRank Problem | Java Solution

Searching Array