// https://github.com/mziccard/node-timsort
|
const DEFAULT_MIN_MERGE = 32;
|
|
const DEFAULT_MIN_GALLOPING = 7;
|
|
type CompareFunc<T> =(a: T, b: T) => number
|
|
function minRunLength(n: number): number {
|
var r = 0;
|
|
while (n >= DEFAULT_MIN_MERGE) {
|
r |= n & 1;
|
n >>= 1;
|
}
|
|
return n + r;
|
}
|
|
function makeAscendingRun<T>(array: T[], lo: number, hi: number, compare: CompareFunc<T>) {
|
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<T>(array, lo, runHi);
|
}
|
else {
|
while (runHi < hi && compare(array[runHi], array[runHi - 1]) >= 0) {
|
runHi++;
|
}
|
}
|
|
return runHi - lo;
|
}
|
|
function reverseRun<T>(array: T[], lo: number, hi: number) {
|
hi--;
|
|
while (lo < hi) {
|
var t = array[lo];
|
array[lo++] = array[hi];
|
array[hi--] = t;
|
}
|
}
|
|
function binaryInsertionSort<T>(array: T[], lo: number, hi: number, start: number, compare: CompareFunc<T>) {
|
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<T>(value: T, array: T[], start: number, length: number, hint: number, compare: CompareFunc<T>) {
|
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<T>(value: T, array: T[], start: number, length: number, hint: number, compare: CompareFunc<T>) {
|
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<T>(array: T[], compare: CompareFunc<T>) {
|
let minGallop = DEFAULT_MIN_GALLOPING;
|
let runStart: number[];
|
let runLength: number[];
|
let stackSize = 0;
|
|
var tmp: T[] = [];
|
|
runStart = [];
|
runLength = [];
|
|
function pushRun(_runStart: number, _runLength: number) {
|
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: number) {
|
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<T>(array[start2], array, start1, length1, 0, compare);
|
start1 += k;
|
length1 -= k;
|
|
if (length1 === 0) {
|
return;
|
}
|
|
length2 = gallopLeft<T>(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: number, length1: number, start2: number, length2: number) {
|
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<T>(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<T>(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();
|
}
|
else {
|
for (i = 0; i < length1; i++) {
|
array[dest + i] = tmp[cursor1 + i];
|
}
|
}
|
}
|
|
function mergeHigh(start1: number, length1: number, start2: number, length2: number) {
|
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<T>(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<T>(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];
|
}
|
}
|
}
|
|
return {
|
mergeRuns,
|
forceMergeRuns,
|
pushRun
|
};
|
}
|
|
export default function sort<T>(
|
array: T[],
|
compare: CompareFunc<T>,
|
lo?: number, hi?: number
|
) {
|
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<T>(array, lo, hi, compare);
|
binaryInsertionSort<T>(array, lo, hi, lo + runLength, compare);
|
return;
|
}
|
|
var ts = TimSort<T>(array, compare);
|
|
var minRun = minRunLength(remaining);
|
|
do {
|
runLength = makeAscendingRun<T>(array, lo, hi, compare);
|
if (runLength < minRun) {
|
var force = remaining;
|
if (force > minRun) {
|
force = minRun;
|
}
|
|
binaryInsertionSort<T>(array, lo, lo + force, lo + runLength, compare);
|
runLength = force;
|
}
|
|
ts.pushRun(lo, runLength);
|
ts.mergeRuns();
|
|
remaining -= runLength;
|
lo += runLength;
|
} while (remaining !== 0);
|
|
ts.forceMergeRuns();
|
}
|
