hackware1993 / chensort Goto Github PK

let maxValue = list[0];
let minValue = maxValue;
for (let i = 1, len = list.length; i < len; ++i) {
    if (list[i] > maxValue) {
        maxValue = list[i];
    }
    if (list[i] < minValue) {
        minValue = list[i];
    }
}

if (maxValue === minValue) {
    return;
}

let bucketSize = Math.min(list.length, 5000);
let maxBucketIndex = bucketSize - 1;

let buckets = new Array(bucketSize);
let slot;

const factor = maxBucketIndex / (maxValue - minValue);
for (let i = 0, len = list.length; i < len; ++i) {
    slot = Math.trunc((list[i] - minValue) * factor);
    if (buckets[slot] === undefined) {
        buckets[slot] = [];
    }
    buckets[slot].push(list[i]);
}

function compare(left, right) {
    return left - right;
}

let index = 0;
for (let i = 0, len = buckets.length; i < len; ++i) {
    if (buckets[i] != null) {
        if (buckets[i].length > 1) {
            if (buckets[i].length >= 1000) {
                chenSort(buckets[i]);
            } else {
                buckets[i].sort(compare);
            }
            for (let element of buckets[i]) {
                list[index++] = element;
            }
        } else {
            list[index++] = buckets[i][0];
        }
    }
}