Radix Sort

function radixSort(arr) {
    // Find the maximum number to determine number of digits
    const max = Math.max(...arr);

    // Get number of digits
    const digits = max.toString().length;

    // Perform counting sort for each digit
    for (let digit = 0; digit < digits; digit++) {
        countingSortByDigit(arr, digit);
    }

    return arr;
}

function countingSortByDigit(arr, digit) {
    const n = arr.length;
    const output = new Array(n);
    const count = new Array(10).fill(0);

    // Count occurrences of each digit (0-9)
    for (let i = 0; i < n; i++) {
        const digitValue = getDigit(arr[i], digit);
        count[digitValue]++;
    }

    // Cumulative count
    for (let i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }

    // Build output array
    for (let i = n - 1; i >= 0; i--) {
        const digitValue = getDigit(arr[i], digit);
        output[count[digitValue] - 1] = arr[i];
        count[digitValue]--;
    }

    // Copy back to original array
    for (let i = 0; i < n; i++) {
        arr[i] = output[i];
    }
}

function getDigit(num, digit) {
    return Math.floor(Math.abs(num) / Math.pow(10, digit)) % 10;
}

How Radix Sort Works

Radix Sort processes numbers digit by digit, using a stable sort (like counting sort) for each digit position. It can work from either the least significant digit (LSD) or most significant digit (MSD).

Algorithm Steps (LSD Radix Sort):

1. Find Maximum: Determine the number with most digits
2. For Each Digit Position: Starting from least significant digit
3. Extract Digit: Get the digit at current position for each number
4. Stable Sort: Use counting sort to sort by current digit
5. Repeat: Move to next more significant digit
6. Complete: Array is sorted after processing all digits

Digit Positions:

• Units Place (10⁰): Rightmost digit
• Tens Place (10¹): Second digit from right
• Hundreds Place (10²): Third digit from right
• Pattern: Each position represents power of 10

Key Characteristics:

• Stable: Maintains relative order of equal elements
• Non-comparison: Doesn't compare elements directly
• Linear time: O(nk) where k is the number of digits
• Integer-based: Works best with positive integers

Variants:

• LSD Radix Sort: Least Significant Digit first (most common)
• MSD Radix Sort: Most Significant Digit first (more complex)
• In-Place Radix Sort: Memory-efficient variants
• Binary Radix Sort: For binary numbers (fewer buckets)

Real-World Applications:

• String sorting: Sorting words by alphabetical order
• IP addresses: Sorting network addresses
• Phone numbers: Sorting contact lists
• ID numbers: Sorting by identification numbers
• Postal codes: Sorting by zip/postal codes

Performance Insights:

• Time Complexity: O(nk) where k is the average number of digits
• Space Complexity: O(n + k) for counting arrays
• Stable: Maintains order of equal elements
• Parallel-friendly: Each digit position can be processed independently

Comparison with Other Sorts:

• vs Counting Sort: Extension to handle multiple digits
• vs Comparison Sorts: Linear time vs O(n log n)
• vs Bucket Sort: Similar concept but different implementation