Radix Sort

Radix Sort

Radix sort is a non-comparative integer sorting algorithm. Its core idea is to sort integers digit by digit, processing from the Least Significant Bit (LSB) to the Most Significant Bit (MSB). Radix sort typically uses a stable sorting algorithm (such as counting sort) as a subroutine to sort each digit.

1. Algorithm Background and Applicable Scenarios

  • Applicable Conditions: Only suitable for integers or data that can be represented as integers (e.g., strings or floating-point numbers require conversion).
  • Time Complexity: O(d·(n + k)), where d is the maximum number of digits, n is the number of elements, and k is the radix (e.g., k=10 for decimal).
  • Space Complexity: O(n + k), requiring extra space to store temporary sorting results.
  • Advantages: When d is small and k is not large, it is more efficient than comparative sorting algorithms (such as quicksort with O(n log n)).

2. Detailed Algorithm Steps

Radix sort consists of the following steps:

Step 1: Determine the Maximum Number of Digits

  • Traverse the array, find the maximum value, and calculate its number of digits, d.
    Example: In the array [170, 45, 75, 90, 802, 24, 2, 66], the maximum value is 802, and the number of digits is 3.

Step 2: Sort Digit by Digit from LSB to MSB

  • Use a stable sorting algorithm (usually counting sort) to sort each digit.
    Key Principle: Higher-order digits have priority over lower-order digits, but sorting must start from the LSB to ensure that sorting higher digits does not disrupt the order already determined by lower digits.

Step 3: Counting Sort Subroutine (Taking Decimal as an Example)

  1. Create a Count Array: Length of 10 (decimal digits 0-9), initialized to 0.
  2. Count Frequencies: Traverse the current digit and count the occurrences of each digit.
  3. Calculate Prefix Sum: Convert the count array into position indices (prefix sum), indicating the final position of each digit in the output array.
  4. Generate Sorted Result: Traverse from the end of the original array forward (to ensure stability). Place elements into the correct positions in a temporary array based on the current digit and the prefix sum array.
  5. Update Array: Copy the temporary array back to the original array, completing the sorting for the current digit.

Step 4: Repeat Steps 2 and 3

  • Repeat the sorting for each digit until the MSB is processed.

3. Example Demonstration

Using the array [170, 45, 75, 90, 802, 24, 2, 66] as an example:

  • Round 1 (Ones place):
    Sort by the ones digit:
    170 (ones digit 0), 90 (0), 802 (2), 2 (2), 24 (4), 45 (5), 75 (5), 66 (6)
    Result: [170, 90, 802, 2, 24, 45, 75, 66]

  • Round 2 (Tens place):
    Sort by the tens digit (preserving the ones digit order):
    802 (tens digit 0), 2 (0), 24 (2), 45 (4), 66 (6), 170 (7), 75 (7), 90 (9)
    Result: [802, 2, 24, 45, 66, 170, 75, 90]

  • Round 3 (Hundreds place):
    Sort by the hundreds digit (preserving the tens and ones digit order):
    2 (hundreds digit 0), 24 (0), 45 (0), 66 (0), 75 (0), 90 (0), 170 (1), 802 (8)
    Final Result: [2, 24, 45, 66, 75, 90, 170, 802]

4. Key Considerations

  • Stability Requirement: The subroutine sorting algorithm must be stable; otherwise, sorting higher digits will disrupt the order already established by lower digits.
  • Handling Negative Numbers: Negative numbers need to be converted to positive numbers (e.g., by adding an offset) or the sign bit must be handled separately.
  • Radix Selection: The radix can be adjusted based on data characteristics (e.g., binary radix k=2) to reduce the number of digits d and improve efficiency.

5. Code Implementation (Pseudocode)

function radixSort(arr):
    max_val = max(arr)
    exp = 1  // Start from the ones place
    
    while max_val // exp > 0:
        countingSortForDigit(arr, exp)
        exp *= 10

function countingSortForDigit(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10  // Decimal digits 0-9
    
    // Count occurrences of the current digit
    for i in range(n):
        digit = (arr[i] // exp) % 10
        count[digit] += 1
    
    // Calculate prefix sum
    for i in range(1, 10):
        count[i] += count[i-1]
    
    // Traverse from the end to ensure stability
    for i in range(n-1, -1, -1):
        digit = (arr[i] // exp) % 10
        output[count[digit] - 1] = arr[i]
        count[digit] -= 1
    
    // Copy back to the original array
    for i in range(n):
        arr[i] = output[i]

6. Summary

Radix sort avoids direct comparison by sorting digit by digit, making it suitable for sorting integers with a limited number of digits. Its efficiency depends on the number of digits d and the radix k. It has significant advantages when the data range is controllable (e.g., sorting phone numbers or ID numbers).