Article Date: 12/20/2018

Merge Sort

Merge Sort is a recursive divide and conquer algorithm. By breaking an array into two smaller halves, MergeSort is a simple yet efficient way to decompose a sorting problem.

A simple visual example is provided as figure 1.1, here the given array has 8 unsorted random numbers: [24, 11, 1, 8, 36, 4, 5, 18]. The first step is to divide the array in the middle and recursively pass each new array: [24, 11, 1, 8] and [36, 4, 5, 18] back to MergeSort respectively. MergeSort will repeat these steps on each new array until the smallest array length of 1 is provided. Once our array reaches the point of length 1, the sorted results are returned.

With each call to MergeSort our array is divided and merged. The ‘merge’ step simply takes a left value and a right value to compare. The lowest or first most value is pushed into our results array accordingly.

Merge Sort
in-Action with Alto.js

When using a divide and conquer algorithm our input size decreases by a factor of two with each level of the recursion. Meaning an input length in level 0 is n, the level-1 recursive calls operate on an array of length n/2, the level-2 recursive calls on arrays of length n/4, and so on.

When there are no more recursive calls, the recursion ‘bottoms out’. We reach this base case when the number of times you need to divide n by 2 before obtaining a number that is at most 1. We would describe our merge-sort algorithm with Big-O Notation as O(n log(n)).