/* Quick multi level mergesort algorithm in javascript * * Sort the array first by field1 then by field 2 */var sort = function(arr) {
var len = arr.length;
if (len < 2) return arr;
var pivot = Math.ceil(len / 2);
return merge(sort(arr.slice(0, pivot)), sort(arr.slice(pivot)));
};
var merge = function(left, right) {
var result = [];
var li = 0;
var ri = 0;
var ll = left.length;
var rl = right.length;
var le = null;
var re = null;
while ((li < ll) && (ri < rl)) {
le = left[li];
re = right[ri];
if (le.field1 > re.field1) {
result.push(le);
li++;
continue;
}
if (le.field1 < re.field1) {
result.push(re);
ri++;
continue;
}
if (le.field2 > re.field2) {
result.push(le);
li++;
continue;
}
result.push(re);
ri++;
continue;
}
result = result.concat(left.slice(li), right.slice(ri));
return result;
};
No comments:
Post a Comment