Radix Sort

Problem Solved

Radix Sort solves the Sorting problem.

Design and Strategy

Radix Sort is a non-comparison-based sorting algorithm that exploits a space–time tradeoff to efficiently sort integers. It processes keys digit by digit, from the least significant digit (LSD) to the most significant. At each digit position, it uses a stable sort—usually Counting Sort—to reorder elements by that digit while preserving the order of elements with equal digits. Each pass is essentially a call to Counting Sort, applied not to the whole key, but to a single digit of each number. If you are not familiar with Counting Sort, you should read that section before continuing.

Let \( n \) be the number of items to sort, \( d \) the number of digits in the largest key (in base \( k \)), and \( k \) the radix (e.g., 10 for decimal). The algorithm performs \( d \) passes—one for each digit position—by looping through \( p = 0 \) to \( d - 1 \).

Each pass uses three arrays:

• Input Array \( A[0 \ldots n-1] \): the original array of keys
• Count Array \( C[0 \ldots k-1] \): counts occurrences of each digit
• Output Array \( B[0 \ldots n-1] \): stores the result after the current pass

The algorithm works as follows:

1. For each digit position \( p = 0 \) to \( d - 1 \), do the following:
   1. Count Digit Occurrences:
      • Initialize \( C[0 \ldots k-1] = 0 \).
      • For each index \( i \) from \( 0 \) to \( n - 1 \):
      • Compute the digit at position \( p \):
        \( d_i = \left\lfloor \frac{A[i]}{k^p} \right\rfloor \bmod k \)
      • Increment the corresponding count: \( C[d_i] = C[d_i] + 1 \)
   2. Prefix Sum:
      For \( j = 1 \) to \( k-1 \), set \( C[j] = C[j] + C[j-1] \) to determine final positions.
   3. Stable Placement:
      Traverse \( A \) from right to left. For each \( A[i] \), compute \( d_i \), decrement \( C[d_i] \), and set \( B[C[d_i]] = A[i] \).
   4. Prepare for Next Pass:
      Copy \( B \) back to \( A \).

As previously mentioned, steps a through c are just a modified version of Counting Sort.

Implementation in Java, C++, Python

public void radixSort(int[] A) {
    int n = A.length;

    // Find maximum value
    int max = A[0];
    for (int i = 1; i < n; i++) {
        if (A[i] > max) max = A[i];
    }

    int[] B = new int[n];

    // Process each digit using exp = 1, 10, 100, ...
    for (int exp = 1; max / exp > 0; exp *= 10) {
        int[] C = new int[10];

        // Phase 1: Count digit occurrences
        for (int i = 0; i < n; i++) {
            int digit = (A[i] / exp) % 10;
            C[digit]++;
        }

        // Phase 2: Compute prefix sums
        for (int i = 1; i < 10; i++) {
            C[i] += C[i - 1];
        }

        // Phase 3: Stable placement into B
        for (int i = n - 1; i >= 0; i--) {
            int digit = (A[i] / exp) % 10;
            B[--C[digit]] = A[i];
        }

        // Copy back for next pass
        System.arraycopy(B, 0, A, 0, n);
    }
}

void radixSort(int A[], int n) {
    // Find maximum value
    int maxv = A[0];
    for (int i = 1; i < n; i++) {
        if (A[i] > maxv) maxv = A[i];
    }

    int* B = new int[n];

    // Process each digit using exp = 1, 10, 100, ...
    for (int exp = 1; maxv / exp > 0; exp *= 10) {
        int C[10] = {0};

        // Phase 1: Count digit occurrences
        for (int i = 0; i < n; i++) {
            int digit = (A[i] / exp) % 10;
            C[digit]++;
        }

        // Phase 2: Compute prefix sums
        for (int i = 1; i < 10; i++) {
            C[i] += C[i - 1];
        }

        // Phase 3: Stable placement into B
        for (int i = n - 1; i >= 0; i--) {
            int digit = (A[i] / exp) % 10;
            B[--C[digit]] = A[i];
        }

        // Copy back for next pass
        for (int i = 0; i < n; i++) {
            A[i] = B[i];
        }
    }

    delete[] B;
}

def radix_sort(A):
    if not A:
        return A

    n = len(A)

    # Find maximum value
    maxv = A[0]
    for x in A:
        if x > maxv:
            maxv = x

    B = [0] * n
    exp = 1

    # Process each digit using exp = 1, 10, 100, ...
    while maxv // exp > 0:
        C = [0] * 10

        # Phase 1: Count digit occurrences
        for x in A:
            digit = (x // exp) % 10
            C[digit] += 1

        # Phase 2: Compute prefix sums
        for i in range(1, 10):
            C[i] += C[i - 1]

        # Phase 3: Stable placement into B
        for i in range(n - 1, -1, -1):
            digit = (A[i] // exp) % 10
            C[digit] -= 1
            B[C[digit]] = A[i]

        # Copy back for next pass
        A = B[:]
        exp *= 10

    return A

Time and Space Analysis

Before analyzing Radix Sort’s performance, we introduce three key parameters: Let \(n\) be the number of keys to sort, \(k\) the radix (number of buckets per digit, e.g. 10 for decimal or 256 for byte-values), and \(d\) the number of digit positions in the largest key (for a maximum key of value \(M\), roughly \(\lfloor \log_{k} M\rfloor + 1\)).

Time Complexity: Each pass of Radix Sort processes one digit position. It consists of four phases, each touching either the input array \(A\) or the count array \(C\):

1. Counting Phase: Scan \(A[0\ldots n-1]\). For each key, extract the current digit in \(O(1)\) and increment the corresponding bucket in \(C\).
   Cost: \(\Theta(n)\).
2. Prefix-Sum Phase: Transform \(C[0\ldots k-1]\) into cumulative counts so each entry indicates its endpoint in the output array.
   Cost: \(\Theta(k)\).
3. Placement Phase: Traverse \(A\) backwards, recompute each digit, decrement its count, and write the key into the output buffer \(B\), preserving stability.
   Cost: \(\Theta(n)\).
4. Copy-Back Phase: Copy \(B[0\ldots n-1]\) back into \(A\) to prepare for the next digit pass.
   Cost: \(\Theta(n)\).

Summing these four phases gives \(\Theta(3n + k)\) work per pass, which simplifies to \(\Theta(n + k)\).

Radix Sort makes one such digit pass for each of the \(d\) digits in the largest key. Therefore, the total running time is
\(\Theta\bigl(d \times (n + k)\bigr)\).

Space Complexity: Aside from the input array, Radix Sort requires:

• An output buffer \(B\) of size \(n\), for \(\Theta(n)\) extra space.
• A count array \(C\) of size \(k\), for \(\Theta(k)\) extra space.
• A constant number of scalar variables, for \(O(1)\) extra space.

Variations/Improvements

• Trade-Offs and Practical Notes
  • Radix size vs. passes: A larger \(k\) (e.g. 256) reduces the number of passes \(d\) but increases the size of the count array \(C\) and may hurt cache performance.
  • Small-radix benefits: A small \(k\) (e.g. 10) often fits entirely in cache, improving real-world speed despite requiring more passes.
  • When \(k\) is much larger than \(n\): If the number of buckets \(k\) exceeds the number of keys \(n\), then the cost to initialize and scan the count array—\(\Theta(k)\)—can outweigh the work on the data itself (\(\Theta(n)\)). In that case, Radix Sort may perform worse than comparison-based algorithms like Quick Sort.
  • Copy-back optimization: Alternating between two buffers or swapping pointers can eliminate the \(\Theta(n)\) copy-back cost per pass at the expense of more complex buffer management.
  • Stability requirement: Each pass relies on a stable sort of one digit (e.g.\ Counting Sort) to preserve the order of equal-digit keys and ensure correctness.
• MSD (Most Significant Digit) Variant: Instead of processing from least to most significant digit, the MSD approach partitions the array by the most significant digit first, then recursively sorts each bucket on the next digit. This naturally handles variable-length keys and can terminate early on buckets whose elements share identical prefixes.
• Radix Selection: Choosing the radix \(k\) involves a space–time trade-off: using a power-of-two radix (e.g. \(2^8\) or \(2^{16}\)) lets you replace division and modulus operations with fast bit-shifts and masks, but it also increases the memory footprint of the count array.
• In-Place Cycle-Leader Permutation: To eliminate the \(\Theta(n)\) copy-back step, you can compute each element’s final index and rotate cycles of elements in place. This reduces auxiliary space but requires careful index bookkeeping.
• Parallel Implementation: Parallelize counting and placement phases across threads or distributed nodes to improve throughput on large datasets.

Links to Resources

• Wikipedia: Radix Sort
• GeeksforGeeks: Radix Sort
• VisuAlgo: Radix Sort Visualization
• USFCA: Radix Sort Demo