Sha256: 05679393431ebb41d4cfa9f449571abf381f8ef4f05160903481f6257a56120f
Contents?: true
Size: 1.23 KB
Versions: 69
Compression:
Stored size: 1.23 KB
Contents
/**
* Merge sort (http://en.wikipedia.org/wiki/Merge_sort)
*/
function mergeSort(arr, compareFn) {
if (arr == null) {
return [];
} else if (arr.length < 2) {
return arr;
}
if (compareFn == null) {
compareFn = defaultCompare;
}
var mid, left, right;
mid = ~~(arr.length / 2);
left = mergeSort( arr.slice(0, mid), compareFn );
right = mergeSort( arr.slice(mid, arr.length), compareFn );
return merge(left, right, compareFn);
}
function defaultCompare(a, b) {
return a < b ? -1 : (a > b? 1 : 0);
}
function merge(left, right, compareFn) {
var result = [];
while (left.length && right.length) {
if (compareFn(left[0], right[0]) <= 0) {
// if 0 it should preserve same order (stable)
result.push(left.shift());
} else {
result.push(right.shift());
}
}
if (left.length) {
result.push.apply(result, left);
}
if (right.length) {
result.push.apply(result, right);
}
return result;
}
module.exports = mergeSort;
Version data entries
69 entries across 69 versions & 2 rubygems