Skip to content

Instantly share code, notes, and snippets.

@mpereira mpereira/merge_sort.js
Last active May 14, 2017

Embed
What would you like to do?
Merge sort implementation in JavaScript.
function merge(xs, leftStart, leftEnd, rightStart, rightEnd) {
var i = leftStart;
var j = rightStart;
var merged = [];
var currentLeft, currentRight;
// Merge.
while (i <= leftEnd || j <= rightEnd) {
currentLeft = xs[i];
currentRight = xs[j];
if ((currentLeft <= currentRight || j > rightEnd) && i <= leftEnd) {
merged.push(currentLeft);
i++;
} else if ((currentLeft > currentRight || i > leftEnd) && j <= rightEnd) {
merged.push(currentRight);
j++;
}
}
var k;
// Update source array.
for (k = 0; k <= rightEnd - leftStart; k++) {
xs[k + leftStart] = merged[k];
}
}
function mergeSort0(xs, start, end) {
var middle = Math.ceil((end - start) / 2);
var leftStart = start;
var leftEnd = Math.max(start, middle - 1);
var rightEnd = end;
var rightStart = Math.min(rightEnd, leftEnd + 1);
if (leftStart !== rightEnd) {
mergeSort0(xs, leftStart, leftEnd);
mergeSort0(xs, rightStart, rightEnd);
merge(xs, leftStart, leftEnd, rightStart, rightEnd);
}
return(xs);
}
function mergeSort(xs) {
if (xs.length <= 1) {
return(xs);
}
return(mergeSort0(xs, 0, xs.length - 1));
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.