Javascript Algorithms — Merge Sort

In this post of the Javascript Algorithms series, we’re going to talk about merge sort. Merge sort is another comparison sorting algorithm that runs in linearithmic, or O(n log n), time. While the run time of merge sort is similar to that of quicksort, quicksort is typically preferred in practice for most problems as the hidden constant value is smaller and allows it to run 2–3x faster. However, mergesort is usually preferred for sorting a linked-list as mergesort doesn’t depend on random access to elements like quicksort does (allowing it to take advantage of linked-lists strengths in sequential access and insertion).

Merge sort is based off of the divide & conquer principal, which essentially means that you divide large, complicated problems into smaller, easier-to-solve problems, and then combine their answers to get the answer to the original problem. By doing this, you halve the size of the input that is being worked on during each iteration.

With merge sort, the first step is to recursively divide the input in halve, leaving you with 2x as many input elements of 1/2 length during every iteration (e.g. if you have a list of length 4, after one iteration you’ll have 2 lists of length 2, then 4 lists of length 1). This happens until the input is broken down into multiple lists of size 1, which are trivially sorted (because any list with only one element…