Skip to content

Instantly share code, notes, and snippets.

@danlourenco
Created August 17, 2016 15:36
Show Gist options
  • Save danlourenco/a40a54773189db59a8d526341b7bf2b2 to your computer and use it in GitHub Desktop.
Save danlourenco/a40a54773189db59a8d526341b7bf2b2 to your computer and use it in GitHub Desktop.
Merge Sort in Javascript
function mergeSort(arr) {
//base case
if (arr.length < 2) return arr;
var halfLength = Math.ceil(arr.length / 2);
var leftSide = arr.splice(0, halfLength);
var rightSide = arr; // just to keep mental model simple
return _stitch(mergeSort(leftSide), mergeSort(rightSide));
}
function _stitch(left, right) {
var results = [];
console.log('left is: ', left);
console.log('right is: ', right);
while (left.length && right.length) {
if (left[0] <= right[0]) {
results.push(left.shift());
}
else {
results.push(right.shift());
}
}
while(left.length) {
results.push(left.shift());
}
while(right.length) {
results.push(right.shift());
}
return results;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment