Radix Sort

Tags

Radix Sort

Category

Sorting

Difficulty

Hard

Problem Statement

Implement Radix Sort to sort an array of non-negative integers. Radix Sort is a non-comparative sorting algorithm that sorts integers by processing individual digits, from the least significant digit to the most significant digit.

Intuition

Instead of comparing elements, Radix Sort exploits the structure of integer representations. By sorting on each digit position using a stable sub-sort (typically Counting Sort), digits in higher positions preserve the order established by lower positions. After processing all digit positions, the array is fully sorted.

Approach

  1. Find the maximum value in the array to determine the number of digit positions to process.
  2. For each digit position (starting from the ones place):
    • Use Counting Sort as a stable sort on the current digit.
    • Counting Sort: build a count array of size 10 (digits 0-9), convert to cumulative counts, then place elements into an output array in stable order.
    • Copy the output array back to the original (or swap references).
  3. Repeat until all digit positions are processed.

Pseudocode

function radixSort(array):
    if length(array) == 0:
        return array

    maxVal = max(array)
    digit = 1    // represents the current place (1, 10, 100, ...)

    while maxVal / digit > 0:
        countingSortByDigit(array, digit)
        digit *= 10

    return array

function countingSortByDigit(array, digit):
    count = array of size 10, filled with 0
    output = array of size length(array)

    for num in array:
        d = (num / digit) % 10
        count[d] += 1

    for i from 1 to 9:
        count[i] += count[i - 1]

    for i from length(array) - 1 down to 0:
        d = (array[i] / digit) % 10
        count[d] -= 1
        output[count[d]] = array[i]

    copy output into array

Time & Space Complexity

  • Time: O(d * n) where d is the number of digits in the maximum value and n is the number of elements. Since d = O(log(maxVal)), this is O(n * log(maxVal)). For fixed-width integers, d is a constant, yielding O(n).
  • Space: O(n + k) where k = 10 (the digit range). Effectively O(n) for the output array.

Key Insights

  • Radix Sort is not comparison-based, so it bypasses the O(n log n) comparison-sort lower bound.
  • Stability of the sub-sort (Counting Sort) is essential. If the sub-sort is unstable, previously sorted digit positions get scrambled.
  • The algorithm processes digits from least significant to most significant (LSD Radix Sort). An MSD variant also exists but is more complex due to recursion.
  • For uniformly distributed data with bounded values, Radix Sort can outperform comparison sorts in practice.

Edge Cases

  • Empty array: return immediately.
  • All elements are the same: Counting Sort places them all in the same bucket, preserving order.
  • Single element: trivially sorted.
  • Array contains 0: handled naturally since 0 % 10 == 0.
  • Very large maximum value: increases the number of passes (d), which can make Radix Sort slower than O(n log n) sorts for large ranges with few elements.

Linked mentions