Every great algorithm has components that make it work. For radix sort, the crucial component is counting sort—a simple yet powerful algorithm that sorts elements in linear time when the range of values is limited. Understanding how counting sort operates as radix sort's subroutine illuminates both algorithms and reveals why their combination is so effective.

In the previous page, we established that radix sort performs multiple passes, each sorting by one digit position. We emphasized that stability is critical for LSD radix sort's correctness. Now we'll see why counting sort is the perfect choice for each pass: it's naturally stable, runs in O(n + k) time where k is the number of distinct digit values, and uses only simple array operations.

Before diving into how counting sort serves radix sort, let's understand counting sort as a standalone algorithm.

The problem counting sort solves:

Given an array of n elements where each element is an integer in the range [0, k-1], sort the array in O(n + k) time.

Why can counting sort beat O(n log n)?

Comparison-based sorting algorithms like merge sort and quicksort have a lower bound of Ω(n log n) because they gain at most 1 bit of information per comparison. Counting sort sidesteps this bound because it doesn't use comparisons. Instead, it uses each element's actual value to determine its position directly.

This is analogous to the difference between:

• Sorting cards by repeatedly comparing pairs (comparison-based)
• Having 52 labeled slots and placing each card directly in its slot (counting-based)

The core insight:

If we know that a value x appears in the array, and we know exactly how many values are less than x, we know exactly where x should be placed in the sorted output.

For example, if x = 5 and there are exactly 7 values less than 5 in the array, then x belongs at index 7 (0-indexed). If there are multiple copies of 5, they belong at indices 7, 8, 9, ... The challenge is computing, for each value, how many values are smaller—which is exactly what counting accomplishes.

Counting sort operates in three distinct phases, each building on the previous. Understanding these phases is crucial for seeing how stability emerges and how the algorithm achieves linear time.

Detailed trace through counting sort:

Let's trace sorting [3, 1, 4, 1, 5, 9, 2, 6] with k = 10:

Input: [3, 1, 4, 1, 5, 9, 2, 6]

PHASE 1: COUNT
count[0] = 0, count[1] = 2, count[2] = 1, count[3] = 1
count[4] = 1, count[5] = 1, count[6] = 1, count[9] = 1

count = [0, 2, 1, 1, 1, 1, 1, 0, 0, 1]
         0  1  2  3  4  5  6  7  8  9

PHASE 2: ACCUMULATE
count = [0, 2, 3, 4, 5, 6, 7, 7, 7, 8]
         0  1  2  3  4  5  6  7  8  9

Reading: 2 elements ≤ 1, 3 elements ≤ 2, 4 elements ≤ 3, etc.
This means: value 1 should occupy indices 0-1, value 2 at index 2,
value 3 at index 3, value 4 at index 4, value 5 at index 5, etc.

PHASE 3: PLACE (backwards iteration)
i=7: arr[7]=6, count[6]=7→6, output[6]=6  →  [_, _, _, _, _, _, 6, _]
i=6: arr[6]=2, count[2]=3→2, output[2]=2  →  [_, _, 2, _, _, _, 6, _]
i=5: arr[5]=9, count[9]=8→7, output[7]=9  →  [_, _, 2, _, _, _, 6, 9]
i=4: arr[4]=5, count[5]=6→5, output[5]=5  →  [_, _, 2, _, _, 5, 6, 9]
i=3: arr[3]=1, count[1]=2→1, output[1]=1  →  [_, 1, 2, _, _, 5, 6, 9]
i=2: arr[2]=4, count[4]=5→4, output[4]=4  →  [_, 1, 2, _, 4, 5, 6, 9]
i=1: arr[1]=1, count[1]=1→0, output[0]=1  →  [1, 1, 2, _, 4, 5, 6, 9]
i=0: arr[0]=3, count[3]=4→3, output[3]=3  →  [1, 1, 2, 3, 4, 5, 6, 9]

Final output: [1, 1, 2, 3, 4, 5, 6, 9] ✓

The backwards iteration in Phase 3 is crucial for stability—but why? This is a subtle point that deserves careful analysis.

Recall the stability requirement:

A stable sort preserves the relative order of elements with equal keys. If element A appears before element B in the input, and they have the same key, then A should appear before B in the output.

The mechanics of cumulative counting:

After Phase 2, count[v] represents the number of elements ≤ v, which is also the position after where the last element with value v should be placed.

When we place an element with value v:

1. We decrement count[v] to get the actual position
2. We place the element at that position
3. The next element with value v (if any) will get the previous position

Why backwards?

Consider elements with the same value v. When iterating backwards:

• The last occurrence in the input gets placed at the highest position for value v
• The second-to-last occurrence gets the second-highest position
• The first occurrence (encountered last) gets the lowest position

This means elements with equal keys maintain their original relative order!

Alternative formulation for stability:

Some implementations count positions differently to enable forward iteration while maintaining stability. Instead of cumulative counts representing positions after each value's block, they represent positions before:

# Alternative Phase 2: Prefix sum of counts
for i in range(1, k):
    count[i] = count[i - 1]  # Position BEFORE (not including) current value

# Alternative Phase 3: Forward iteration
for i in range(n):
    val = arr[i]
    output[count[val]] = val
    count[val] += 1  # Move to next position for this value

Both formulations achieve stability; the key is consistency between how counts are computed and how elements are placed.

Now we connect the pieces: how does radix sort use counting sort as its subroutine?

The key adaptation:

In standalone counting sort, we sort by the element's value directly. In radix sort's use of counting sort, we sort by the digit at a specific position. The element itself is preserved—only the key used for sorting changes.

Execution trace of the integration:

Input: [329, 457, 657, 839, 436, 720, 355]

Pass 1: Sorting by digit at position 0 (1s place)
  Digits: [9, 7, 7, 9, 6, 0, 5]
  Counting sort groups by these digits:
    0: [720]
    5: [355]
    6: [436]
    7: [457, 657]  ← Note: 457 before 657 (original order preserved)
    9: [329, 839]  ← Note: 329 before 839 (original order preserved)
  Result: [720, 355, 436, 457, 657, 329, 839]

Pass 2: Sorting by digit at position 1 (10s place)
  Digits: [2, 5, 3, 5, 5, 2, 3]
  Counting sort groups by these digits (preserving order from Pass 1):
    2: [720, 329]  ← 720 was first in Pass 1 result
    3: [436, 839]  ← 436 was first in Pass 1 result
    5: [355, 457, 657]  ← Order from Pass 1 preserved
  Result: [720, 329, 436, 839, 355, 457, 657]

Pass 3: Sorting by digit at position 2 (100s place)
  Digits: [7, 3, 4, 8, 3, 4, 6]
  Counting sort groups by these digits (preserving order from Pass 2):
    3: [329, 355]  ← 329 before 355 because of earlier passes!
    4: [436, 457]  ← 436 before 457 because of earlier passes!
    6: [657]
    7: [720]
    8: [839]
  Result: [329, 355, 436, 457, 657, 720, 839]  ✓ SORTED

Understanding the complexity of radix sort requires analyzing both the outer loop (radix sort itself) and the inner operations (counting sort at each pass).

Counting sort complexity analysis:

For each pass of counting sort on n elements with digit range [0, k-1]:

• Phase 1 (Count): O(n) — one pass through input array
• Phase 2 (Accumulate): O(k) — one pass through count array
• Phase 3 (Place): O(n) — one pass through input array
• Space: O(n + k) — output array of size n, count array of size k

Total per pass: O(n + k) time, O(n + k) space

Radix sort complexity analysis:

If we have d digit positions and use radix/base k:

• Number of passes: d
• Work per pass: O(n + k)
• Total time: O(d × (n + k))
• Total space: O(n + k) (reused across passes)

The relationship between d and k:

For a maximum value M in the input:

• With base k, we need d = ⌈log_k(M + 1)⌉ digits
• Larger k means fewer passes (smaller d) but larger count arrays
• Smaller k means more passes but smaller count arrays

Example calculations:

For 32-bit integers (M up to ~4 billion):

Real-world radix sort implementations incorporate several optimizations beyond the basic algorithm:

1. Skip unnecessary passes:

If all numbers fit in fewer digits than the maximum, skip the higher-order passes:

def radix_sort_optimized(arr, base=256):
    if not arr:
        return arr
    
    max_val = max(arr)
    
    position = 0
    exp = 1
    result = arr[:]
    
    # Only iterate while there's a significant digit to process
    while max_val // exp > 0:
        result = counting_sort_by_digit(result, position, base)
        exp *= base
        position += 1
    
    return result

2. In-place counting sort:

The standard counting sort requires O(n) extra space for the output array. For some applications, we can use an in-place variant (though it's more complex and the output space is often acceptable).

3. Combining base choices:

Some implementations use different bases for different passes, optimizing cache behavior. For example, use base 256 for lower-order bytes and base 65536 for higher-order portions when n is large enough to amortize the larger count array.

4. Hybrid sorting:

For small subarrays (especially in MSD radix sort's recursive calls), switch to insertion sort. The overhead of counting sort for very small arrays can exceed the benefit.

We've established that radix sort needs a stable subroutine. Counting sort is the standard choice, but other stable sorts exist. Why is counting sort preferred?

Comparison with other stable sorting algorithms:

The critical observation:

If we used merge sort as the subroutine and had d digit positions:

• Total time: O(d × n log n)
• For d = 4: O(4 n log n) = O(n log n)

This is no better than just using merge sort directly! The whole point of radix sort is to achieve O(d(n+k)) which, for fixed d and k, is O(n).

Counting sort's O(n + k) complexity is essential because:

1. k is small (at most the radix, typically 256)
2. This makes each pass effectively O(n)
3. Total complexity O(d × n) ≈ O(n) for fixed d

Could we use bucket sort?

Yes! Bucket sort is essentially counting sort with lists instead of counts, then concatenation. Some implementations prefer this view:

def bucket_sort_by_digit(arr, position, base):
    buckets = [[] for _ in range(base)]
    
    for num in arr:
        digit = get_digit(num, position, base)
        buckets[digit].append(num)  # Automatically stable!
    
    result = []
    for bucket in buckets:
        result.extend(bucket)
    
    return result

This is equivalent to counting sort but uses more memory (list overhead) and has worse cache behavior. For large n, counting sort's array-based approach is faster.

We've explored how counting sort serves as the engine powering radix sort's remarkable performance. This symbiotic relationship exemplifies elegant algorithm design: two specialized algorithms combining to solve a broader problem than either could alone.

What's next:

Now that we understand both the overall radix sort algorithm and its counting sort subroutine, we're ready to analyze the complete time complexity: O(d × (n + k)). The next page will dissect this expression, showing how it compares to O(n log n) algorithms and when radix sort truly shines.