Merge Sort Made Easy! (Code Meditation)

  • Can it get better than this for a comparison-based sorting algorithm? No.
  • So Why wait? let’s learn this ASAP and accurately.
  • We will also look at the shortcomings of Merge Sort at a later point.
Source

The Gist

The idea is simple, just split the array at a midpoint (which I will show you how to calculate) and simply call the function on itself, meaning further split each array until you reach a case where you have a single item in an array to work with. This is called the base case. Once you reach the base case, you merge all single element arrays (base cases) from bottom to the top of the recursion tree using an algorithm called merge algorithm (which I will be explaining). Why wait? let’s jump right into the code and I'll try my best to explain every line step by step.

Code:

Interesting facts about Merge Sort

  • MergeSort is a divide and conquer algorithm, we are splitting array and recursively working on individual subparts.
  • Merge sort needs O(n) amount of memory in order to copy over elements as it sorts. You might have noticed this as we were creating left and right sub-arrays every time. This is probably the greatest drawback of the merge sort algorithm: it is an out-of-place sorting algorithm, that requires additional memory as its dataset grows.
  • Merge sort can work well on any type of data sets irrespective of its size.

Complexity Analysis

One way to solve recurrences is to draw a recursion tree where each node in the tree represents a subproblem and the value at each node represents the amount of work spent at each subproblem.

Source

Final Comments

java.util.Arrays uses quicksort (actually dual-pivot quicksort in the most recent version) for primitive types such as int and mergesort (modified) for objects that implement Comparable or use a Comparator. Why the difference? Why not pick one and use it for all cases? Robert Sedgewick suggests that

Resources:

--

--

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
Achyuth Nandikotkur

Achyuth Nandikotkur

Passionately Curious. Believer in Simplicity. Humble Writer.