25 - Merge Sort (A Challenge)

[GitHub Repo for this challenge]

Merge Sort utilizes recursion and divide & conquer to get the job done.

No Googling code or solutions, try this one yourself! There is a lot of supporting material available on this page.

The algorithms for Bubble, Selection, and Insert sort are all very linear. They traverse the array one element at a time in a specific direction. Instead, we can break the array down into smaller pieces (in fact, down to the individual items) and when we traverse back up the tree, we can sort as we go. This creates a much faster sorting process. Here's an animation and still image from Wikipedia:

In the still image you can see a "top-down" approach where we separate the sorting process into 'threads'. Each thread gets separated into indifidual items (single-element arrays). The green arrows are showing the return portion of the algorithm. The sorting happens along the return by copying the data into a new temporary array (we do not modify the original).

• Here is the algorithm in action with playing cards.

• Here is the algorithm in action as a folk dance (I recommend speeding this one up).

• And here is a very math-heavy one describing how it works

• Explanation and pseudocode (great resource)

Merge Sort utilizes three functions:

• mergeSort(list) { to start things off }

• mergeSortHelper(list, from, to, tempList) { this is the recursive one }

• merge(list, from, mid, to, tempList) { for putting the pieces back together }

Name the functions what you want, but essentially mergeSortHelper is the recursive function. tempList starts as an empty array (same length as list) in which we place the sorted data. Note that we do not sort in place - which means we don't touch the original array. The merge function copies, "merges", the data back together into tempList.

Where to Start:

A. mergeSort(list): Here we generate an empty array that is the same length as list and begin the recursive process:

// Generate an empty array of correct length

let temp = new Array(list.length);

mergeSortHelper(list, 0, list.length - 1, temp);

B. mergeSortHelper(list, from, to, tempList): Here we need to accomplish 4 things, assuming we have work to do (ie. until the base case is found).

1. Find the middle index (round if necessary) in order to split the current values into "left" and "right".

2. Recurse on the left half, in order to split it.

3. Recurse on the right halve, in order to split it.

4. Merge the two sides back together into tempList in a sorted order.

C. merge(list, from, mid, to, tempList): One-by-one, copy from list to tempList in a sorted order. Lowest first, then the next, then the next. The values from, mid, and to are to assist with keeping track of where to begin and end.

Head over to GitHub and implement the mergeSort algorithm using JavaScript and the details given above.