Needed a good implementation of a merge sort algorithm in JavaScript and found that the ones available out there are not great in terms of optimizing for performance. Also could not find one that used ES6 syntax. I wrote this version on Node version 7.4 which has good ES6 coverage.

A couple of things seemed to dramatically impact performance over other versions I came across. One performance tweak is instantiating the array in the merge function using "new Array(length)" syntax. Since you know it will be the length of the two input arrays combined you can specify that upfront. The other tweak was using 3 separate while loops instead of concatenating arrays for the return in the merge function. You can see the basic idea of how this works in this gist.

If you are not familiar with merge sort, it uses a divide and conquer type of strategy. I think this video is pretty helpful to get the basic idea. You can change the settings to slow the playback and see what's happening in more detail.

Anyway, I found this JavaScript version of merge sort to be significantly faster than what I found out there so I figured I would post it....

function mergeSort(input) { const conquer = (a, b) => { const aLen = a.length; const bLen = b.length; const result = new Array(aLen + bLen); let aIndex = 0; let bIndex = 0; let rIndex = 0; while (aIndex < aLen && bIndex < bLen) { const aVal = a[aIndex]; const bVal = b[bIndex]; if (aVal < bVal) { result[rIndex] = aVal; aIndex++; } else { result[rIndex] = bVal; bIndex++; } rIndex++; } while (aIndex < aLen && bIndex < bLen) { const aVal = a[aIndex]; const bVal = b[bIndex]; if (aVal < bVal) { result[rIndex] = aVal; aIndex++; } else { result[rIndex] = bVal; bIndex++; } rIndex++; } while (aIndex < aLen) { result[rIndex] = a[aIndex]; aIndex++; rIndex++; } while (bIndex < bLen) { result[rIndex] = b[bIndex]; bIndex++; rIndex++; } return result; }; const divide = (arr) => { const len = arr.length; if (len <= 1) { return arr; } const mid = Math.floor(len / 2); return conquer(divide(arr.slice(0, mid)), divide(arr.slice(mid))); }; return divide(input); }