123456789101112131415161718192021222324252627282930313233343536373839404142434445 |
- // TODO: use something more complex like timsort?
- var floor = Math.floor;
-
- var mergeSort = function (array, comparefn) {
- var length = array.length;
- var middle = floor(length / 2);
- return length < 8 ? insertionSort(array, comparefn) : merge(
- mergeSort(array.slice(0, middle), comparefn),
- mergeSort(array.slice(middle), comparefn),
- comparefn
- );
- };
-
- var insertionSort = function (array, comparefn) {
- var length = array.length;
- var i = 1;
- var element, j;
-
- while (i < length) {
- j = i;
- element = array[i];
- while (j && comparefn(array[j - 1], element) > 0) {
- array[j] = array[--j];
- }
- if (j !== i++) array[j] = element;
- } return array;
- };
-
- var merge = function (left, right, comparefn) {
- var llength = left.length;
- var rlength = right.length;
- var lindex = 0;
- var rindex = 0;
- var result = [];
-
- while (lindex < llength || rindex < rlength) {
- if (lindex < llength && rindex < rlength) {
- result.push(comparefn(left[lindex], right[rindex]) <= 0 ? left[lindex++] : right[rindex++]);
- } else {
- result.push(lindex < llength ? left[lindex++] : right[rindex++]);
- }
- } return result;
- };
-
- module.exports = mergeSort;
|