Continuing to evaluate efficient sorting algorithms, today we’ll look at merge sort. Merge sort^{[1]} is a comparison sort using a divide and conquer algorithm, developed by John von Neumann^{[2]} in 1945. It recursively divides the list into smaller sublists of length one, then repeatedly merges the sublists in order until there is only one sublist left. It has a worst case runtime of (O(*n*log*n*)), making it worst-case more efficient than Quicksort.

### How do it…

Merge sort needs two functions, the first is a function to merge two ordered

arrays together:

function fnMerge(aLeft, aRight){ var aResult = [], iLeft = 0, iRight = 0; // iterate until one array is empty while (iLeft < aLeft.length && iRight < aRight.length) { // push the next ordered value on the resulting array // and increment its counter if (aLeft[iLeft] < aRight[iRight]) { aResult.push(aLeft[iLeft++]); } else { aResult.push(aRight[iRight++]); } } // join any remaining values from the two arrays into the results array return aResult.concat(aLeft.slice(iLeft)).concat(aRight.slice(iRight)); }

The second function is the public merge sort function that recursively splits the array into smaller halves before calling the merge function:

function fnMergeSort(aList) { // zero or 1 length arrays are already sorted if (2 > aList.length) { return aList; } var iMiddle = Math.floor(aList.length / 2); return fnMerge( fnMergeSort(aList.slice(0, iMiddle)), fnMergeSort(aList.slice(iMiddle))); }

This visual is a little harder, but it shows each step of the splitting and merging functions:

Restart merge sort With a New Array

If we take a 10,000 element array and sort it, here is how merge sort compares to native array sort (prints to the console):

### How it works…

The merge sort algorithm recursively breaks the array into smaller subarrays by splitting the arrays in half, until all subarrays are length one or zero. By their nature (having only one or zero element), these subarrays are sorted. The algorithm then recursively merges the sub arrays together in order. As each subarray is combined the new subarray is ordered from the two merging subarrays, resulting eventually in one final sorted array. Since the same steps need to be taken regardless of how *sorted* the original array was, merge sort has an average, best, and worst case runtime of O(*n*log*n*).

The merging function accepts two sorted subarrays and merges them together into a new sorted array. We solve this by iterating until one array is fully merged, using index trackers on each array, and inserting the greater value into the merged array on each iteration. Since both lists are in order, we know that when the iteration stops, all uncompared elements in the second array are greater than the already joined elements, so we can just concatenate the remaining elements at the end^{[3]}. Rather than using an `if`

statement to concatenate the right subarray, we just concatenate the remaining elements of both arrays, so the fully merged array will concatenate zero elements, and the other will concatenate all unmerged elements.

The merge sort function accepts a single array and splits it into two relatively even subarrays (if the array has an odd length, one subarray may be an element larger than the other). Those subarrays are each passed to the merge sort function and the results of the recursive merge sorts are joined using the merge function. Thus eventually, returning a single sorted array. The recursive calls stop when the subarrays are all of length one or zero.

### There’s more…

If it is important that your merge sort function modifies the passed in array, you can use the following technique to splice the new elements into the original array^{[3]}:

function fnMergeSort(aList) { // zero or 1 length arrays are already sorted if (2 > aList.length) { return aList; } var iMidIndex = Math.floor(aList.length / 2); var aParams = fnMerge( fnMergeSort(aList.slice(0, iMidIndex)), fnMergeSort(aList.slice(iMidIndex))); // put arguments one and two of the splice function into the // front of aParams, remaining arguments are elements to splice in aParams.unshift(0, aList.length); aList.splice.apply(aList, aParams); }

Here we’ve used the `splice`

function to replace all the elements in the provide array with the sorted elements, so that the originally provided list is modified, instead of returning a new sorted array. The signature of the `splice`

function is the start index, the length to splice, and any number of elements to insert to replace the range we are splicing over. As such, we `unshift`

the start index and length for the splice to the front of the array of sorted elements, so that we can use the `apply`

function to properly pass everything into the `splice`

function, which has a signature startIndex

, lengthOfSplice

, firstElementToSpliceIn

, …, nthElementToSpliceIn

.