Skip to content

Instantly share code, notes, and snippets.

@liamgriffiths
Last active January 1, 2016 22:59
Show Gist options
  • Save liamgriffiths/8213542 to your computer and use it in GitHub Desktop.
Save liamgriffiths/8213542 to your computer and use it in GitHub Desktop.
// merge sort
// https://en.wikipedia.org/wiki/Merge_sort
var sort = function(list) {
// if list contains one element, it is sorted
if (list.length <= 1) return list;
// divide list in half into 2 sublists
var middle = Math.floor(list.length / 2);
var left = list.slice(0, middle);
var right = list.slice(middle);
// sort the sublists
left = sort(left);
right = sort(right);
// merge the sublists
return merge(left, right);
};
var merge = function(a, b) {
var result = [];
while (a.length || b.length) {
if (a.length && b.length) {
if (a[0] <= b[0]) {
result.push(a.shift());
} else {
result.push(b.shift());
}
} else if (a.length) {
result.push(a.shift());
} else if (b.length) {
result.push(b.shift());
}
}
return result;
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment