Radix Sort

function radixSort(arr) {
    // Find the maximum number to know number of digits
    const max = Math.max(...arr);
    
    // Do counting sort for every digit
    // exp is 10^i where i is current digit number
    for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {
        countingSort(arr, exp);
    }
    
    return arr;
}

function countingSort(arr, exp) {
    const n = arr.length;
    const output = new Array(n); // Output array
    const count = new Array(10).fill(0); // Count array for digits 0-9
    
    // Store count of occurrences of each digit
    for (let i = 0; i < n; i++) {
        const digit = Math.floor(arr[i] / exp) % 10;
        count[digit]++;
    }
    
    // Change count[i] so that it contains actual position
    // of this digit in output[]
    for (let i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }
    
    // Build the output array
    // Process from right to left to maintain stability
    for (let i = n - 1; i >= 0; i--) {
        const digit = Math.floor(arr[i] / exp) % 10;
        output[count[digit] - 1] = arr[i];
        count[digit]--;
    }
    
    // Copy the output array to arr[], so that arr[] now
    // contains sorted numbers according to current digit
    for (let i = 0; i < n; i++) {
        arr[i] = output[i];
    }
}

// Optimized version for different bases
function radixSortBase(arr, base = 10) {
    const max = Math.max(...arr);
    
    for (let exp = 1; Math.floor(max / exp) > 0; exp *= base) {
        countingSortBase(arr, exp, base);
    }
    
    return arr;
}

function countingSortBase(arr, exp, base) {
    const n = arr.length;
    const output = new Array(n);
    const count = new Array(base).fill(0);
    
    // Count occurrences of each digit in given base
    for (let i = 0; i < n; i++) {
        const digit = Math.floor(arr[i] / exp) % base;
        count[digit]++;
    }
    
    // Convert counts to positions
    for (let i = 1; i < base; i++) {
        count[i] += count[i - 1];
    }
    
    // Build output array (stable)
    for (let i = n - 1; i >= 0; i--) {
        const digit = Math.floor(arr[i] / exp) % base;
        output[count[digit] - 1] = arr[i];
        count[digit]--;
    }
    
    // Copy back to original array
    for (let i = 0; i < n; i++) {
        arr[i] = output[i];
    }
}

// Example usage:
const numbers = [170, 45, 75, 90, 2, 802, 24, 66];
console.log("Original:", numbers);
radixSort(numbers);
console.log("Sorted:", numbers);