Skip to content

Instantly share code, notes, and snippets.

@mbenford
Created April 14, 2015 23:12
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save mbenford/cc94d116b2575e8111d2 to your computer and use it in GitHub Desktop.
Save mbenford/cc94d116b2575e8111d2 to your computer and use it in GitHub Desktop.
Merge sort in Javascript
function mergesort(array) {
return sort(array, 0, array.length - 1);
function sort(array, start, end) {
if (start === end) return [array[start]];
var middle = Math.floor((start + end) / 2);
return merge(sort(array, start, middle), sort(array, middle + 1, end));
}
function merge(left, right) {
var result = [],
leftIndex = 0,
rightIndex = 0;
while (leftIndex < left.length && rightIndex < right.length) {
if (left[leftIndex] <= right[rightIndex]) {
result.push(left[leftIndex]);
leftIndex++;
}
else {
result.push(right[rightIndex]);
rightIndex++;
}
}
while (leftIndex < left.length) {
result.push(left[leftIndex]);
leftIndex++;
}
while (rightIndex < right.length) {
result.push(right[rightIndex]);
rightIndex++;
}
return result;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment