123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666 |
- // https://github.com/mziccard/node-timsort
- var DEFAULT_MIN_MERGE = 32;
- var DEFAULT_MIN_GALLOPING = 7;
- var DEFAULT_TMP_STORAGE_LENGTH = 256;
- function minRunLength(n) {
- var r = 0;
- while (n >= DEFAULT_MIN_MERGE) {
- r |= n & 1;
- n >>= 1;
- }
- return n + r;
- }
- function makeAscendingRun(array, lo, hi, compare) {
- var runHi = lo + 1;
- if (runHi === hi) {
- return 1;
- }
- if (compare(array[runHi++], array[lo]) < 0) {
- while (runHi < hi && compare(array[runHi], array[runHi - 1]) < 0) {
- runHi++;
- }
- reverseRun(array, lo, runHi);
- } else {
- while (runHi < hi && compare(array[runHi], array[runHi - 1]) >= 0) {
- runHi++;
- }
- }
- return runHi - lo;
- }
- function reverseRun(array, lo, hi) {
- hi--;
- while (lo < hi) {
- var t = array[lo];
- array[lo++] = array[hi];
- array[hi--] = t;
- }
- }
- function binaryInsertionSort(array, lo, hi, start, compare) {
- if (start === lo) {
- start++;
- }
- for (; start < hi; start++) {
- var pivot = array[start];
- var left = lo;
- var right = start;
- var mid;
- while (left < right) {
- mid = left + right >>> 1;
- if (compare(pivot, array[mid]) < 0) {
- right = mid;
- } else {
- left = mid + 1;
- }
- }
- var n = start - left;
- switch (n) {
- case 3:
- array[left + 3] = array[left + 2];
- case 2:
- array[left + 2] = array[left + 1];
- case 1:
- array[left + 1] = array[left];
- break;
- default:
- while (n > 0) {
- array[left + n] = array[left + n - 1];
- n--;
- }
- }
- array[left] = pivot;
- }
- }
- function gallopLeft(value, array, start, length, hint, compare) {
- var lastOffset = 0;
- var maxOffset = 0;
- var offset = 1;
- if (compare(value, array[start + hint]) > 0) {
- maxOffset = length - hint;
- while (offset < maxOffset && compare(value, array[start + hint + offset]) > 0) {
- lastOffset = offset;
- offset = (offset << 1) + 1;
- if (offset <= 0) {
- offset = maxOffset;
- }
- }
- if (offset > maxOffset) {
- offset = maxOffset;
- }
- lastOffset += hint;
- offset += hint;
- } else {
- maxOffset = hint + 1;
- while (offset < maxOffset && compare(value, array[start + hint - offset]) <= 0) {
- lastOffset = offset;
- offset = (offset << 1) + 1;
- if (offset <= 0) {
- offset = maxOffset;
- }
- }
- if (offset > maxOffset) {
- offset = maxOffset;
- }
- var tmp = lastOffset;
- lastOffset = hint - offset;
- offset = hint - tmp;
- }
- lastOffset++;
- while (lastOffset < offset) {
- var m = lastOffset + (offset - lastOffset >>> 1);
- if (compare(value, array[start + m]) > 0) {
- lastOffset = m + 1;
- } else {
- offset = m;
- }
- }
- return offset;
- }
- function gallopRight(value, array, start, length, hint, compare) {
- var lastOffset = 0;
- var maxOffset = 0;
- var offset = 1;
- if (compare(value, array[start + hint]) < 0) {
- maxOffset = hint + 1;
- while (offset < maxOffset && compare(value, array[start + hint - offset]) < 0) {
- lastOffset = offset;
- offset = (offset << 1) + 1;
- if (offset <= 0) {
- offset = maxOffset;
- }
- }
- if (offset > maxOffset) {
- offset = maxOffset;
- }
- var tmp = lastOffset;
- lastOffset = hint - offset;
- offset = hint - tmp;
- } else {
- maxOffset = length - hint;
- while (offset < maxOffset && compare(value, array[start + hint + offset]) >= 0) {
- lastOffset = offset;
- offset = (offset << 1) + 1;
- if (offset <= 0) {
- offset = maxOffset;
- }
- }
- if (offset > maxOffset) {
- offset = maxOffset;
- }
- lastOffset += hint;
- offset += hint;
- }
- lastOffset++;
- while (lastOffset < offset) {
- var m = lastOffset + (offset - lastOffset >>> 1);
- if (compare(value, array[start + m]) < 0) {
- offset = m;
- } else {
- lastOffset = m + 1;
- }
- }
- return offset;
- }
- function TimSort(array, compare) {
- var minGallop = DEFAULT_MIN_GALLOPING;
- var length = 0;
- var tmpStorageLength = DEFAULT_TMP_STORAGE_LENGTH;
- var stackLength = 0;
- var runStart;
- var runLength;
- var stackSize = 0;
- length = array.length;
- if (length < 2 * DEFAULT_TMP_STORAGE_LENGTH) {
- tmpStorageLength = length >>> 1;
- }
- var tmp = [];
- stackLength = length < 120 ? 5 : length < 1542 ? 10 : length < 119151 ? 19 : 40;
- runStart = [];
- runLength = [];
- function pushRun(_runStart, _runLength) {
- runStart[stackSize] = _runStart;
- runLength[stackSize] = _runLength;
- stackSize += 1;
- }
- function mergeRuns() {
- while (stackSize > 1) {
- var n = stackSize - 2;
- if (n >= 1 && runLength[n - 1] <= runLength[n] + runLength[n + 1] || n >= 2 && runLength[n - 2] <= runLength[n] + runLength[n - 1]) {
- if (runLength[n - 1] < runLength[n + 1]) {
- n--;
- }
- } else if (runLength[n] > runLength[n + 1]) {
- break;
- }
- mergeAt(n);
- }
- }
- function forceMergeRuns() {
- while (stackSize > 1) {
- var n = stackSize - 2;
- if (n > 0 && runLength[n - 1] < runLength[n + 1]) {
- n--;
- }
- mergeAt(n);
- }
- }
- function mergeAt(i) {
- var start1 = runStart[i];
- var length1 = runLength[i];
- var start2 = runStart[i + 1];
- var length2 = runLength[i + 1];
- runLength[i] = length1 + length2;
- if (i === stackSize - 3) {
- runStart[i + 1] = runStart[i + 2];
- runLength[i + 1] = runLength[i + 2];
- }
- stackSize--;
- var k = gallopRight(array[start2], array, start1, length1, 0, compare);
- start1 += k;
- length1 -= k;
- if (length1 === 0) {
- return;
- }
- length2 = gallopLeft(array[start1 + length1 - 1], array, start2, length2, length2 - 1, compare);
- if (length2 === 0) {
- return;
- }
- if (length1 <= length2) {
- mergeLow(start1, length1, start2, length2);
- } else {
- mergeHigh(start1, length1, start2, length2);
- }
- }
- function mergeLow(start1, length1, start2, length2) {
- var i = 0;
- for (i = 0; i < length1; i++) {
- tmp[i] = array[start1 + i];
- }
- var cursor1 = 0;
- var cursor2 = start2;
- var dest = start1;
- array[dest++] = array[cursor2++];
- if (--length2 === 0) {
- for (i = 0; i < length1; i++) {
- array[dest + i] = tmp[cursor1 + i];
- }
- return;
- }
- if (length1 === 1) {
- for (i = 0; i < length2; i++) {
- array[dest + i] = array[cursor2 + i];
- }
- array[dest + length2] = tmp[cursor1];
- return;
- }
- var _minGallop = minGallop;
- var count1;
- var count2;
- var exit;
- while (1) {
- count1 = 0;
- count2 = 0;
- exit = false;
- do {
- if (compare(array[cursor2], tmp[cursor1]) < 0) {
- array[dest++] = array[cursor2++];
- count2++;
- count1 = 0;
- if (--length2 === 0) {
- exit = true;
- break;
- }
- } else {
- array[dest++] = tmp[cursor1++];
- count1++;
- count2 = 0;
- if (--length1 === 1) {
- exit = true;
- break;
- }
- }
- } while ((count1 | count2) < _minGallop);
- if (exit) {
- break;
- }
- do {
- count1 = gallopRight(array[cursor2], tmp, cursor1, length1, 0, compare);
- if (count1 !== 0) {
- for (i = 0; i < count1; i++) {
- array[dest + i] = tmp[cursor1 + i];
- }
- dest += count1;
- cursor1 += count1;
- length1 -= count1;
- if (length1 <= 1) {
- exit = true;
- break;
- }
- }
- array[dest++] = array[cursor2++];
- if (--length2 === 0) {
- exit = true;
- break;
- }
- count2 = gallopLeft(tmp[cursor1], array, cursor2, length2, 0, compare);
- if (count2 !== 0) {
- for (i = 0; i < count2; i++) {
- array[dest + i] = array[cursor2 + i];
- }
- dest += count2;
- cursor2 += count2;
- length2 -= count2;
- if (length2 === 0) {
- exit = true;
- break;
- }
- }
- array[dest++] = tmp[cursor1++];
- if (--length1 === 1) {
- exit = true;
- break;
- }
- _minGallop--;
- } while (count1 >= DEFAULT_MIN_GALLOPING || count2 >= DEFAULT_MIN_GALLOPING);
- if (exit) {
- break;
- }
- if (_minGallop < 0) {
- _minGallop = 0;
- }
- _minGallop += 2;
- }
- minGallop = _minGallop;
- minGallop < 1 && (minGallop = 1);
- if (length1 === 1) {
- for (i = 0; i < length2; i++) {
- array[dest + i] = array[cursor2 + i];
- }
- array[dest + length2] = tmp[cursor1];
- } else if (length1 === 0) {
- throw new Error(); // throw new Error('mergeLow preconditions were not respected');
- } else {
- for (i = 0; i < length1; i++) {
- array[dest + i] = tmp[cursor1 + i];
- }
- }
- }
- function mergeHigh(start1, length1, start2, length2) {
- var i = 0;
- for (i = 0; i < length2; i++) {
- tmp[i] = array[start2 + i];
- }
- var cursor1 = start1 + length1 - 1;
- var cursor2 = length2 - 1;
- var dest = start2 + length2 - 1;
- var customCursor = 0;
- var customDest = 0;
- array[dest--] = array[cursor1--];
- if (--length1 === 0) {
- customCursor = dest - (length2 - 1);
- for (i = 0; i < length2; i++) {
- array[customCursor + i] = tmp[i];
- }
- return;
- }
- if (length2 === 1) {
- dest -= length1;
- cursor1 -= length1;
- customDest = dest + 1;
- customCursor = cursor1 + 1;
- for (i = length1 - 1; i >= 0; i--) {
- array[customDest + i] = array[customCursor + i];
- }
- array[dest] = tmp[cursor2];
- return;
- }
- var _minGallop = minGallop;
- while (true) {
- var count1 = 0;
- var count2 = 0;
- var exit = false;
- do {
- if (compare(tmp[cursor2], array[cursor1]) < 0) {
- array[dest--] = array[cursor1--];
- count1++;
- count2 = 0;
- if (--length1 === 0) {
- exit = true;
- break;
- }
- } else {
- array[dest--] = tmp[cursor2--];
- count2++;
- count1 = 0;
- if (--length2 === 1) {
- exit = true;
- break;
- }
- }
- } while ((count1 | count2) < _minGallop);
- if (exit) {
- break;
- }
- do {
- count1 = length1 - gallopRight(tmp[cursor2], array, start1, length1, length1 - 1, compare);
- if (count1 !== 0) {
- dest -= count1;
- cursor1 -= count1;
- length1 -= count1;
- customDest = dest + 1;
- customCursor = cursor1 + 1;
- for (i = count1 - 1; i >= 0; i--) {
- array[customDest + i] = array[customCursor + i];
- }
- if (length1 === 0) {
- exit = true;
- break;
- }
- }
- array[dest--] = tmp[cursor2--];
- if (--length2 === 1) {
- exit = true;
- break;
- }
- count2 = length2 - gallopLeft(array[cursor1], tmp, 0, length2, length2 - 1, compare);
- if (count2 !== 0) {
- dest -= count2;
- cursor2 -= count2;
- length2 -= count2;
- customDest = dest + 1;
- customCursor = cursor2 + 1;
- for (i = 0; i < count2; i++) {
- array[customDest + i] = tmp[customCursor + i];
- }
- if (length2 <= 1) {
- exit = true;
- break;
- }
- }
- array[dest--] = array[cursor1--];
- if (--length1 === 0) {
- exit = true;
- break;
- }
- _minGallop--;
- } while (count1 >= DEFAULT_MIN_GALLOPING || count2 >= DEFAULT_MIN_GALLOPING);
- if (exit) {
- break;
- }
- if (_minGallop < 0) {
- _minGallop = 0;
- }
- _minGallop += 2;
- }
- minGallop = _minGallop;
- if (minGallop < 1) {
- minGallop = 1;
- }
- if (length2 === 1) {
- dest -= length1;
- cursor1 -= length1;
- customDest = dest + 1;
- customCursor = cursor1 + 1;
- for (i = length1 - 1; i >= 0; i--) {
- array[customDest + i] = array[customCursor + i];
- }
- array[dest] = tmp[cursor2];
- } else if (length2 === 0) {
- throw new Error(); // throw new Error('mergeHigh preconditions were not respected');
- } else {
- customCursor = dest - (length2 - 1);
- for (i = 0; i < length2; i++) {
- array[customCursor + i] = tmp[i];
- }
- }
- }
- this.mergeRuns = mergeRuns;
- this.forceMergeRuns = forceMergeRuns;
- this.pushRun = pushRun;
- }
- function sort(array, compare, lo, hi) {
- if (!lo) {
- lo = 0;
- }
- if (!hi) {
- hi = array.length;
- }
- var remaining = hi - lo;
- if (remaining < 2) {
- return;
- }
- var runLength = 0;
- if (remaining < DEFAULT_MIN_MERGE) {
- runLength = makeAscendingRun(array, lo, hi, compare);
- binaryInsertionSort(array, lo, hi, lo + runLength, compare);
- return;
- }
- var ts = new TimSort(array, compare);
- var minRun = minRunLength(remaining);
- do {
- runLength = makeAscendingRun(array, lo, hi, compare);
- if (runLength < minRun) {
- var force = remaining;
- if (force > minRun) {
- force = minRun;
- }
- binaryInsertionSort(array, lo, lo + force, lo + runLength, compare);
- runLength = force;
- }
- ts.pushRun(lo, runLength);
- ts.mergeRuns();
- remaining -= runLength;
- lo += runLength;
- } while (remaining !== 0);
- ts.forceMergeRuns();
- }
- module.exports = sort;
|