Skip to content

Instantly share code, notes, and snippets.

@primaryobjects

primaryobjects/mergesort.js

Last active January 20, 2017 23:53
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 primaryobjects/6f502f0a2546bfb4fb2c60905dae22f0 to your computer and use it in GitHub Desktop.
Save primaryobjects/6f502f0a2546bfb4fb2c60905dae22f0 to your computer and use it in GitHub Desktop.
Download ZIP
Merge Sort implemented in javascript. Demo at http://jsbin.com/hinotelaca/edit?js,console
Raw
mergesort.js
function mergeSort(arr) {
var result = [];
// Calculate mid point to split array.
var mid = Math.floor(arr.length / 2);
var left = arr.slice(0, mid);
var right = arr.slice(mid, arr.length);
// If more than one element, split the array again, until we get to a single element (implicitly sorted).
if (left.length > 1) {
left = mergeSort(left);
}
if (right.length > 1) {
right = mergeSort(right);
}
// Merge the left and right parts together, until either part is exhausted.
while (left.length > 0 && right.length > 0) {
var value;
// Sort the values while merging.
if (left[0] < right[0]) {
value = left.splice(0, 1)[0];
}
else {
value = right.splice(0, 1)[0];
}
result.push(value);
}
// Add in the remaining values from the left-over group.
if (left.length > 0) {
result = result.concat(left);
}
else if (right.length > 0) {
result = result.concat(right);
}
return result;
}
Raw
zexample.js
var arr = [3,2,1,12,62,7,5,4,100,88,97,39];
console.log('Sorting: ' + arr);
console.log(mergeSort(arr));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment