Radix Sort

Radix sort is a non-comparison integer sorting algorithm that processes the input one digit at a time (or one byte, bit-field, or other fixed-width chunk), using a stable sort like Counting Sort as the inner per-digit subroutine. For n integers each d digits wide in base b, it runs in O(d × (n + b)) time. By picking b = O(n) and noting d is constant for a fixed-width key (e.g., d = 4 bytes for a 32-bit integer with b = 256), radix sort achieves O(n) total time on bounded-width keys — beating the Ω(n log n) comparison-sort lower bound. Historically, radix sort is the original automated sort: Herman Hollerith’s 1880s punch-card tabulating machines for the U.S. Census did exactly this, sorting cards one digit-column at a time using mechanical pin-and-bin sorters. Today it lives on in GPU sorts (CUDA Thrust, NVIDIA CUB, where massively parallel histogram + scan operations make radix sort dominant), in specialized database sorts (column stores sorting integer keys), and as a teaching example of how exploiting key structure can break information-theoretic comparison bounds.

1. Intuition — Sorting Mail by ZIP Code

You have a sack of letters and want them in ZIP code order, where ZIPs are 5-digit numbers like 90210.

Naive: look at each pair of ZIPs, compare them whole, O(n log n) letters per comparison sort.
Mailroom-style radix sort (LSD — least significant digit):
1. Set up 10 mailbins labeled 0 through 9.
2. Pass 1. Look only at the rightmost digit of each letter’s ZIP. Drop each letter into the bin matching that digit. Then collect all bins in order (0 first, then 1, then 2, …, 9). The letters are now sorted by ones digit.
3. Pass 2. Look only at the tens digit. Drop into bins again, then collect. Now sorted by tens digit, with ties broken by ones digit (because we kept the ones-digit order from pass 1 — this requires the bin-collection step to be stable).
4. Pass 3, 4, 5: repeat for hundreds, thousands, ten-thousands.
5. After 5 passes, the entire sack is sorted by full ZIP code.

The cleverness: each pass is just O(n) work to bin and collect (10 bins, n letters). After 5 passes, total work is 5n = O(n). We never compared two ZIP codes — we just bucketed by digits and concatenated.

The reason it works: stability. Each pass preserves the relative order of any two letters that had equal current digits, so the lower-digit information stays intact as higher digits are sorted. Without stability, pass 2 would scramble pass 1’s work and the algorithm would be wrong.

There is also an MSD (most significant digit) variant — sort by leftmost digit first, then recursively sort each bucket by the next digit — but LSD is the iconic version and the easier to reason about.

2. Tiny Worked Example (n = 6, base 10, d = 3)

Sort [170, 045, 075, 090, 802, 024, 002, 066] (8 numbers, each ≤ 999, in base 10). We’ll do LSD radix sort: pass 1 = ones digit, pass 2 = tens digit, pass 3 = hundreds digit. Each pass uses Counting Sort internally, which is stable.

Pass 1: sort by ones digit

Ones digits: [0, 5, 5, 0, 2, 4, 2, 6].

After stable sort by ones digit:

Original ones-digit:  [0,   5,   5,   0,   2,   4,   2,   6 ]
Original values:      [170, 045, 075, 090, 802, 024, 002, 066]

Sorted by ones digit (stable: equal-ones keep input order):
Output: [170, 090, 802, 002, 024, 045, 075, 066]
   ones: [0,   0,   2,   2,   4,   5,   5,   6 ]

Notice 170 precedes 090 because 170 came first in the input (both have ones-digit 0). Same for 802 vs 002 and 045 vs 075. Stability preserved.

Pass 2: sort by tens digit (using output of Pass 1 as input)

Tens digits of [170, 090, 802, 002, 024, 045, 075, 066]: [7, 9, 0, 0, 2, 4, 7, 6].

After stable sort by tens digit:

Output: [802, 002, 024, 045, 066, 170, 075, 090]
  tens: [0,   0,   2,   4,   6,   7,   7,   9 ]

Within tens-digit-0, 802 precedes 002 (was their order from pass 1). Within tens-digit-7, 170 precedes 075 (also their pass-1 order). Stability is cumulative — pass 2 preserves what pass 1 established.

Pass 3: sort by hundreds digit

Hundreds digits of [802, 002, 024, 045, 066, 170, 075, 090]: [8, 0, 0, 0, 0, 1, 0, 0].

After stable sort by hundreds digit:

Output: [002, 024, 045, 066, 075, 090, 170, 802]
hundred: [0,   0,   0,   0,   0,   0,   1,   8]

This is the final sorted order: 2, 24, 45, 66, 75, 90, 170, 802. Verified.

The cleverness becomes apparent: after sorting by the most significant digit, the lower-digit ordering already established by previous passes is preserved within each hundreds-digit group. The stable sort property is the linchpin.

Total work: 3 passes × (8 elements + 10-bin counting sort) = O(d (n + b)) = O(3 × 18) = O(54). For comparison, an O(n log n) comparison sort would do 8 log₂ 8 = 24 comparisons — fewer total operations, but each comparison is more expensive (multi-byte compare) than a digit extraction. At scale, radix sort wins on bounded keys.

3. Pseudocode

radix_sort_lsd(arr, b):                           # b = base / radix
    if arr is empty: return
    max_val := max(arr)
    exp := 1                                      # current digit's place value
    while max_val / exp > 0:
        arr := counting_sort_by_digit(arr, exp, b)
        exp := exp * b

counting_sort_by_digit(arr, exp, b):              # sort by digit (arr[i] / exp) mod b
    n := length(arr)
    count := array of zeros, length b
    output := array of length n

    # Phase 1: count occurrences of each digit
    for x in arr:
        digit := (x / exp) mod b
        count[digit] := count[digit] + 1

    # Phase 2: prefix sum → exclusive end positions
    for i from 1 to b - 1:
        count[i] := count[i] + count[i - 1]

    # Phase 3: place right-to-left for stability
    for i from n - 1 down to 0:
        digit := (arr[i] / exp) mod b
        count[digit] := count[digit] - 1
        output[count[digit]] := arr[i]

    return output

The (x / exp) mod b extracts the digit at place exp. For exp = 1 it’s the ones digit; exp = 10 the tens; exp = 100 the hundreds; and so on. The outer while loop iterates as long as there’s any value with a higher digit, which is d = ⌊log_b(max_val)⌋ + 1 iterations.

4. Python Implementation

def counting_sort_by_digit(arr: list[int], exp: int, b: int = 10) -> list[int]:
    """Stable counting sort of arr by the digit at place value `exp` in base `b`."""
    n = len(arr)
    count = [0] * b
    output = [0] * n
 
    # Phase 1: count
    for x in arr:
        digit = (x // exp) % b
        count[digit] += 1
 
    # Phase 2: prefix sum
    for i in range(1, b):
        count[i] += count[i - 1]
 
    # Phase 3: place right-to-left for stability
    for i in range(n - 1, -1, -1):
        digit = (arr[i] // exp) % b
        count[digit] -= 1
        output[count[digit]] = arr[i]
 
    return output
 
 
def radix_sort(arr: list[int], b: int = 10) -> list[int]:
    """LSD radix sort of non-negative integers in base `b`. Stable."""
    if not arr:
        return []
    if min(arr) < 0:
        raise ValueError("LSD radix sort requires non-negative integers; "
                         "split into negatives and non-negatives first")
    max_val = max(arr)
    out = list(arr)
    exp = 1
    while max_val // exp > 0:
        out = counting_sort_by_digit(out, exp, b)
        exp *= b
    return out

Calling radix_sort([170, 45, 75, 90, 802, 24, 2, 66]) returns [2, 24, 45, 66, 75, 90, 170, 802]. With b = 256 (sort by byte) and 32-bit integer inputs, we’d do 4 passes regardless of the values’ magnitudes — O(4 × (n + 256)) = O(n + 1024) = O(n) for n larger than a few thousand.

A more practical implementation uses bytes rather than decimal digits, since CPUs naturally handle byte-aligned data faster. Setting b = 256 and exp advancing by factors of 256 is the standard production choice for sorting 32-bit or 64-bit integer keys.

4.1 Handling Negative Integers

LSD radix sort with the above formulation only works for non-negative integers. For signed integers, two common approaches:

Split-and-merge: separate negatives and non-negatives, sort each by absolute value, then assemble with negatives reversed.
Bias trick: add 2^(w-1) to each w-bit signed integer to make all values non-negative (mapping the signed range [-2^(w-1), 2^(w-1) - 1] into [0, 2^w - 1]), sort, then subtract the bias back. This works because the order-preserving bias makes radix sort comparison-equivalent.
Two’s-complement bit-flip: flip the sign bit of each input integer; sort lexicographically by bytes; flip back. Works because two’s-complement signed integers sort almost as unsigned, with only the sign bit inverted.

For floating-point IEEE 754, a similar bit-twiddling trick exists: flip the sign bit for non-negatives, flip all bits for negatives, then radix sort, then reverse the transformations.

5. Complexity

5.1 Time

O(d × (n + b)), where:

n = number of items
d = number of digits per item (in the chosen radix)
b = the radix (size of the per-pass count array)

Each of the d passes is one Counting Sort on the current digit, costing O(n + b). Multiplying gives O(d(n + b)).

5.2 When Radix Sort Beats Comparison Sorts

For fixed-width integer keys (e.g., 32-bit int, 64-bit long), d is a small constant — 4 for 32-bit integers in base 256, 8 for 64-bit. With b = 256 and n reasonably large, the total cost is O(d × n) = O(n) — strictly linear in the number of items.

A comparison sort like Quicksort or Tim Sort needs O(n log n) comparisons, and each comparison on a w-bit key is O(w) time (you have to look at the bits to compare). So a comparison sort is really O(w n log n) bit operations. Radix sort with b = 256 is O((w / 8) n) bit operations — beating comparison sorts by a log n factor whenever n is large enough that the constant-factor differences don’t matter.

This is the crisp version of “radix sort is O(n)”: for fixed-width keys at scale, it really is asymptotically faster than any comparison-based sort.

5.3 Why Comparison Sort Lower Bound Doesn’t Apply

The famous Ω(n log n) comparison-sort lower bound is derived from a decision-tree argument: each comparison reveals 1 bit of information about the input ordering, and there are log₂(n!) = Θ(n log n) bits of order information to discover. So Ω(n log n) comparisons are needed.

Radix sort isn’t comparison-based. Each pass uses each input’s digit as a direct array index into a b-bin count array — this is a single log₂(b)-bit query in O(1) time, much richer than a single comparison’s 1 bit. Across d passes, radix sort extracts d × log₂(b) = log₂(b^d) = log₂(k) bits per element, where k = b^d is the size of the key space. For n elements with log₂(n!) ≈ n log₂(n) bits of order to discover, radix sort does n × log₂(k) = n × w bit-extraction operations (where w is key width in bits) — independent of n.

So radix sort breaks the comparison lower bound by using a richer query model (random access by key value) rather than just comparison. This is the same reason Counting Sort beats Ω(n log n). The two algorithms are conceptually one family — counting sort is “radix sort with d = 1” applied to small-range keys.

5.4 Choosing `b` (the Radix)

For a fixed n, the right b minimizes d(n + b) = (log_b(max_val))(n + b). Calculus gives the optimal b ≈ n / ln(2), but in practice the choice is dominated by hardware:

b = 256 (sort by byte) lets you use byte-aligned reads, typically 1 ns per extraction. The most common real-world choice.
b = 65536 (sort by 16-bit halfword) requires a 65536-entry count array, which busts L1 cache. Slower.
b = 1 << 11 ≈ 2048 is sometimes optimal for L1 cache (the count array fits comfortably).

GPU radix sorts (CUB, Thrust) use much smaller b per pass (often b = 16 or b = 32) because thread-level parallelism on the histogram pass favors small bin counts. Merrill & Grimshaw 2011 (“High Performance and Scalable Radix Sorting”) describes the state-of-the-art GPU radix sort design.

5.5 Space

Count array: O(b).
Output buffer: O(n) (counting sort is not in-place).
Total auxiliary: O(n + b).

For b = 256 this is essentially O(n), the same as Merge Sort.

6. LSD vs MSD — Two Variants

6.1 LSD (Least Significant Digit) — the iconic version

Process digits from the least significant (rightmost) to the most significant. Each pass is one full counting sort over the entire array. Stability of the inner sort is what carries lower-digit ordering through subsequent passes.

Simple, iterative, easy to implement.
Sorts fixed-width keys naturally; d is determined upfront.
Works for variable-width keys only with padding (treat shorter keys as having leading zeros — i.e., higher-digit zeros).

This is the version used in production code for integer sorting and the version everyone learns first.

6.2 MSD (Most Significant Digit)

Process digits from the most significant (leftmost) to the least significant. After sorting by the leftmost digit, recursively radix-sort each digit-bucket separately by the next digit.

Naturally handles variable-length keys like strings (sort all the “a…” words, then within each, sort by next character, etc.).
Recursive structure; requires either explicit recursion or a queue of subproblems.
Can short-circuit early on already-distinct keys (no need to look at remaining digits if a bucket has size 1).
More cache-friendly for some workloads because each recursion processes a smaller subset.

MSD radix sort is the canonical algorithm for lexicographic string sorting at scale: sort first by character 0, then within each character-0 bucket sort by character 1, etc. This is essentially a trie-traversal sort and underlies many string-sorting libraries.

6.3 Comparison

Property	LSD	MSD
Direction	Right to left	Left to right
Recursive?	No (iterative)	Yes (recursive on buckets)
Variable-length keys?	Awkward (need padding)	Natural
Early termination?	No (always `d` full passes)	Yes (stop a bucket of size 1)
Use case	Fixed-width integers	Variable-length strings
Stability	Native (inner sort is stable)	Needs care (stable inner sort + recursion order)

7. Historical Background — From Punch Cards to GPUs

Radix sort predates computers. Herman Hollerith invented mechanical card-sorting machines in the 1880s to tabulate the U.S. Census. His machines read 80-column punch cards and routed each card into one of 12 mechanical pockets based on the value of a single column — exactly the per-digit binning of LSD radix sort. To sort cards by a multi-column field, an operator made multiple passes through the machine, sorting by one column per pass, starting from the least significant (rightmost) column. After d passes for a d-column field, the cards were in full sorted order.

This wasn’t called “radix sort” at the time — that name came later, in the 1950s computing literature — but it is the same algorithm. Hollerith’s company eventually became IBM, and electromechanical card sorters dominated business data processing through the 1960s. Generations of bookkeepers and data clerks ran radix sort with their hands and feet for decades before electronic computers existed.

Modern radix sort lives in two niches:

GPU sorting: Massively parallel hardware (NVIDIA CUDA, AMD ROCm) makes the histogram-and-scan operations of radix sort embarrassingly parallel — each thread handles a subset of the input, contributes to a per-warp histogram, and a hierarchical scan combines them. NVIDIA CUB and Thrust use radix sort as the default integer sort, often achieving O(n) throughput limited only by memory bandwidth. For sorting hundreds of millions of integers on a GPU, radix sort is the only competitive choice.
Database column-store sorts: Systems like Vertica, ClickHouse, and DuckDB sort integer columns with radix sort because their workloads frequently have bounded-width integer keys (timestamps, user IDs, product IDs) and benefit from O(n) linear sorting.

Outside these niches, comparison sorts dominate for general-purpose use because the key types are too varied and the constants too unfavorable.

8. When To Use Radix Sort

8.1 Use it when

Keys are integers (or fixed-width bit strings, or anything with stable digit decomposition) and n is large.
You can afford O(n) extra memory.
You’re on a GPU and want to sort millions of keys at memory-bandwidth speed.
You’re building a specialized system (database, numerical library) where the input domain is known to be bounded-width.
You have strings of bounded length and want lexicographic order — MSD radix sort excels.

8.2 Don’t use it when

Keys are arbitrary comparable objects (custom comparators, unbounded types) — comparison sort is the only general option.
Keys are tiny and n is small — a simple Insertion Sort or Quicksort has lower constant overhead.
Memory is tight — radix sort needs O(n) aux. Use Heap Sort for in-place worst-case-bounded.
Keys have enormously variable widths with most being short — LSD’s padding is wasteful.
You need stability with a comparison-required tiebreaker — radix sort by the integer key is stable, but if you need to break ties by another comparator, hybridize with a stable comparison sort.

9. Pitfalls

9.1 Forgetting Stability of the Inner Sort

Radix sort’s correctness requires the per-digit sort to be stable. If you swap Counting Sort for an unstable sort like Quicksort or Heap Sort in the inner loop, the algorithm is incorrect — lower-digit ordering is destroyed by each subsequent pass, and the final result is some random ordering that happens to be sorted only by the most-significant digit. This is one of the most common implementation bugs and the cause of mysterious failures.

9.2 Negative Integers Break the Naive Algorithm

Vanilla LSD radix sort assumes non-negative integers. If your input has negatives, either bias the inputs by adding 2^(w-1), split into negative/non-negative groups, or use a sign-bit-aware variant. Calling unmodified radix sort on [-3, 5, -1, 8] produces nonsense because (-3 // 1) % 10 in Python is 7 (Python’s floor-division for negatives is non-intuitive).

9.3 Floating-Point Keys

IEEE 754 floats can be radix-sorted by reinterpreting their bits as integers, but the sign-bit and the asymmetry between negative and positive floats requires care. The standard trick: for non-negative floats flip the sign bit; for negative floats flip all bits; then radix-sort the resulting unsigned integers; finally reverse the bit-flips. Without these flips, the bit-pattern lexicographic order doesn’t match numerical order.

9.4 Choosing `b` Too Large

A b larger than CPU L1 cache (typically 32 KB) means the count array doesn’t fit in fast cache, and each count[digit] += 1 becomes a cache-miss read-modify-write. For b = 65536 with 4-byte counts, the count array is 256 KB — well past L1, hurting performance. Empirical sweet spot is b = 256 (count array = 1 KB, fits in L1) or b = 1024 (4 KB).

9.5 Variable-Length Strings With LSD

LSD radix sort on strings of unequal length needs padding (treat missing characters as zero or some sentinel). This wastes work and produces ordering quirks if not done carefully. Use MSD for strings — it handles variable lengths naturally and short-circuits when buckets become singletons.

9.6 Treating It As a “Drop-in” Replacement for `sort()`

Radix sort is fast for the cases it’s designed for, but slower than Tim Sort or Quicksort on small arrays, on arrays of arbitrary objects, or on inputs with huge value ranges relative to n. Don’t replace your stdlib sort with radix sort without measuring.

10. Diagram — Three LSD Passes

flowchart LR
    Input["Input<br/>[170,45,75,90,<br/>802,24,2,66]"] --> P1["Pass 1<br/>by ones digit<br/>(stable counting sort)"]
    P1 --> M1["[170,90,802,2,<br/>24,45,75,66]"]
    M1 --> P2["Pass 2<br/>by tens digit"]
    P2 --> M2["[802,2,24,45,<br/>66,170,75,90]"]
    M2 --> P3["Pass 3<br/>by hundreds digit"]
    P3 --> Output["[2,24,45,66,<br/>75,90,170,802]"]

What this diagram shows. LSD radix sort sweeping through the array three times for 3-digit base-10 inputs. Each box between passes shows the array’s intermediate state after stably sorting on the indicated digit. Stability of the per-pass Counting Sort is what guarantees that the lower-digit ordering established in earlier passes survives subsequent passes — within any group of equal-digits-on-the-current-pass, the relative order is exactly what it was at the end of the previous pass, which means the overall ordering after all d passes is a valid full-key sort. The number of passes equals the number of digits in the largest key (3 here, 4 for 32-bit integers in base 256, 8 for 64-bit, etc.), and each pass is O(n + b). Total: O(d(n + b)). With d = O(1) for fixed-width keys and b = O(n), this becomes O(n) — strictly linear, beating any comparison sort’s Ω(n log n).

11. Comparison With Other Sorts

Property	Radix Sort (LSD)	Counting Sort	Merge Sort	Quicksort	Tim Sort
Worst time	O(d(n + b))	O(n + k)	O(n log n)	O(n²)	O(n log n)
Linear on bounded keys?	✅ for fixed-width	✅ for small `k`	❌ (always log-linear)	❌	❌
Comparison-based?	❌	❌	✅	✅	✅
Stable?	✅	✅	✅	❌	✅
In-place?	❌ (O(n) aux)	❌	❌	✅	❌
Adaptive?	❌	❌	❌	❌	✅
Use case	Bounded-width integers, GPU	Small-range integers	General-purpose	General-purpose	Real-world data

The big takeaway: comparison sorts are general-purpose and pay the O(n log n) price for that generality. Radix and counting sorts are specialized — they exploit the structure of integer keys to get O(n), but they don’t work for arbitrary types. In production, comparison sorts dominate because most code sorts heterogeneous data; radix sort dominates only in narrow integer-heavy niches (databases, GPUs, embedded numerical work).

12. Common Interview Problems

Problem	Radix Sort Connection
”Sort `n` 32-bit integers in `O(n)` time”	LSD radix sort with base 256, 4 passes.
”Sort an array of strings of length ≤ `d`”	MSD radix sort, `O(d × n)` for total characters.
”Sort a billion 64-bit integers on a GPU”	LSD radix sort is the standard answer; CUB/Thrust use it.
”Sort dates in YYYYMMDD format”	Radix sort by day, then month, then year — naturally gets sorted dates.
”Why can radix sort be `O(n)` when no comparison sort can?”	Same answer as counting sort: the `Ω(n log n)` lower bound is comparison-specific; radix sort uses array indexing, a richer query.
”Implement string sort in linear time”	MSD radix sort or Trie-based sort.

13. Open Questions

What is the practical break-even n at which LSD radix sort with b = 256 beats Tim Sort for sorting random 32-bit integers? Empirical answer is roughly n ≥ 10⁵ to 10⁶ on modern CPUs, but depends heavily on cache and memory bandwidth.
Can a SIMD-accelerated radix sort approach memory bandwidth limits on contemporary CPUs? Recent work (e.g., AVX-512 implementations) suggests yes, but mainstream stdlibs haven’t adopted these yet.
Is there a stable in-place radix sort with reasonable constants? The American Flag sort and Burstsort are partial answers but have caveats.

14. See Also

Counting Sort — the per-digit subroutine of radix sort
Merge Sort — comparison sort, O(n log n) always, stable
Quicksort — comparison sort, O(n log n) average, in-place
Heap Sort — comparison sort, O(n log n) worst, in-place
Tim Sort — Python/Java’s adaptive comparison sort
Insertion Sort — small-n baseline; comparison-based
Big-O Notation
SWE Interview Preparation MOC

vault

Explorer

Radix Sort

Radix Sort

1. Intuition — Sorting Mail by ZIP Code

2. Tiny Worked Example (n = 6, base 10, d = 3)

Pass 1: sort by ones digit

Pass 2: sort by tens digit (using output of Pass 1 as input)

Pass 3: sort by hundreds digit

3. Pseudocode

4. Python Implementation

4.1 Handling Negative Integers

5. Complexity

5.1 Time

5.2 When Radix Sort Beats Comparison Sorts

5.3 Why Comparison Sort Lower Bound Doesn’t Apply

5.4 Choosing b (the Radix)

5.5 Space

6. LSD vs MSD — Two Variants

6.1 LSD (Least Significant Digit) — the iconic version

6.2 MSD (Most Significant Digit)

6.3 Comparison

7. Historical Background — From Punch Cards to GPUs

8. When To Use Radix Sort

8.1 Use it when

8.2 Don’t use it when

9. Pitfalls

9.1 Forgetting Stability of the Inner Sort

9.2 Negative Integers Break the Naive Algorithm

9.3 Floating-Point Keys

9.4 Choosing b Too Large

9.5 Variable-Length Strings With LSD

9.6 Treating It As a “Drop-in” Replacement for sort()

10. Diagram — Three LSD Passes

11. Comparison With Other Sorts

12. Common Interview Problems

13. Open Questions

14. See Also

Graph View

Table of Contents

Backlinks

5.4 Choosing `b` (the Radix)

9.4 Choosing `b` Too Large

9.6 Treating It As a “Drop-in” Replacement for `sort()`