radixSort

Radix Sort (LSD) with negative numbers

by liormb

JavaScript

function radixSort(arr) {
    const base = 10;
    let divider = 1;
    let maxVal = Number.NEGATIVE_INFINITY;

    while (divider === 1 || divider <= maxVal) {
        const buckets = [...Array(10)].map(() => []);

        for (const val of arr) {
            const positiveVal = Math.abs(val);
            buckets[Math.floor((positiveVal / divider) % base)].push(val);
            maxVal = positiveVal > maxVal ? positiveVal : maxVal;
        }

        arr = [].concat.apply([], buckets);
        divider *= base;
    }
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] < 0) {
            arr.unshift(arr.splice(i, 1)[0]);
        }
    }
    return arr;
}