**Unit ****3**** - Divide & Conquer**

**3****.****4**** - ****Merge Sort**

**3.4 - Merge Sort**

**3.4 - Merge Sort**

"Split Search" was actually "Binary Search". I just didn't want you Googling the answer. **Merge sort **is *not* a codename - that is what it's called. No Googling code or solutions! 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 above, you can see a "top-down" approach where we separate the sorting process into 'threads' that get taken care of in the green arrows (after the halfway point). Those green arrows occur during the *return* portion of the algorithm and the sort is performed by **copying** the data into a **new** array (we do not modify the original).

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

**Merge Sort utilizes three functions:**

**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:**

**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).

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

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

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

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 Replit and implement the mergeSort algorithm using JavaScript and the details given above.