Radix Sort

Radix sort is a non-comparative sorting method in computation and algorithms that orders n keys—such as W-bit integers, IEEE-754 floating-point numbers, or character strings—by decomposing each key into d positional digits written in a chosen base (or radix) b and distributing the keys into b buckets one digit position at a time. Because radix sort determines bucket placement directly from digit values via array indexing rather than pairwise key comparisons (a_i < a_j), it bypasses the information-theoretic Ω(n log n) comparison-tree lower bound and achieves Θ(d · (n + b)) running time—which simplifies to linear Θ(n) time whenever the number of digits d is bounded by a constant and the radix b = O(n).

The physical algorithm predates electronic digital computers by more than half a century: in 1887, American statistician Herman Hollerith patented electromechanical punched-card tabulating and sorting machines for the 1890 United States Census, which sorted card decks column by column from the least significant column to the most significant column so that operators could re-stack the 10 decimal pockets in order after each pass. In 1954, Harold H. Seward formalized random-access memory (RAM) Least Significant Digit (LSD) radix sort in his Massachusetts Institute of Technology Master's thesis by replacing mechanical pockets with a two-pass prefix-sum counting sort array, laying the foundation for modern high-throughput GPU sorting, linear-time suffix array construction for the Burrows–Wheeler transform, and network routing table compilation.

In computational complexity theory, any sorting algorithm that learns the relative order of n distinct elements purely through binary pairwise comparisons (a_i ≤ a_j) can be modeled as a binary decision tree in which each internal node performs one comparison and each leaf represents one of the n! possible permutations of the input. Because a binary tree of height h has at most 2^h leaves, distinguishing all n! permutations requires 2^h ≥ n!, or by Stirling's approximation and Shannon entropy:

h ≥ log₂(n!) = n log₂ n − n log₂ e + (1/2) log₂(2πn) = Ω(n log n)

Radix sort escapes this binary decision tree by exploiting the internal representation of keys on a RAM machine: extracting an r-bit digit from a key and using that digit as an integer index into an array of b = 2^r buckets performs a b-way branch in O(1) time, acquiring r = log₂ b bits of ordering information per memory access instead of 1 bit per pairwise comparison.

1. Least Significant Digit (LSD) Radix Sort

Suppose each key x ∈ {0, 1, ..., b^d − 1} is represented as a d-tuple of base-b digits (x_d−1, x_d−2, ..., x₁, x₀)_b, where:

x = ∑_k=0^d−1 x_k · b^k, with x_k = ⌊x / b^k⌋ mod b ∈ {0, 1, ..., b − 1}

LSD radix sort iterates from the least significant digit k = 0 up to the most significant digit k = d − 1. On pass k, it reorders the entire array of n elements according to digit x_k using a stable auxiliary sort—standardly counting sort—which preserves the relative input order of any two keys whose k-th digits are equal:

1. Histogram Pass (O(n)): Zero the count array C[0..b − 1] in O(b) time, scan the input array A[0..n − 1], and increment C[x_k(A[i])].
2. Exclusive Prefix-Sum Pass (O(b)): Convert C into starting bucket offsets: set *offset*[0] = 0 and *offset*[j] = *offset*[j − 1] + C[j − 1] for j = 1, ..., b − 1.
3. Stable Scatter Pass (O(n)): Scan A[0..n − 1] from left to right, writing each element A[i] with digit v = x_k(A[i]) into the output buffer B[*offset*[v]] and incrementing *offset*[v]. Swap pointers A ↔ B for pass k + 1.

Inductive Proof of Correctness and the Necessity of Stability

Why does sorting from the least significant digit to the most significant digit work? By induction on k, assume that after pass k − 1, the keys are already sorted with respect to their lower k digits (x_k−1, ..., x₀). On pass k, consider any two keys x and y:

• If their k-th digits differ (x_k < y_k), pass k places x in an earlier bucket than y, which is the proper order regardless of their lower digits.
• If their k-th digits are equal (x_k = y_k), their true order is determined by their lower k digits (x_k−1, ..., x₀). Because the inductive hypothesis ensures that x and y arrived at pass k in the proper order of their lower k digits, the stability of counting sort preserves that order inside bucket x_k.

2. Most Significant Digit (MSD) Radix Sort and American Flag Sort

MSD radix sort processes digits in the opposite direction—from the most significant digit k = d − 1 (or the first character of a variable-length string) down to k = 0. Pass 1 partitions the array into b top-level buckets according to the leading digit; thereafter, each non-empty bucket of size > 1 is sorted recursively and independently on the next digit k − 1 like a multi-way divide-and-conquer algorithm (effectively building a traversal of a b-ary trie).

MSD radix sort offers two major advantages for variable-length strings and lexicographic records:

• Early Termination: Whenever a bucket contains 0 or 1 keys (or falls below a threshold such as 16 keys, where it switches to insertion sort), recursion stops without examining the remaining trailing characters.
• In-Place Execution (American Flag Sort): In 1993, Peter M. McIlroy, Keith Bostic, and M. Douglas McIlroy introduced American Flag Sort, an in-place MSD radix sort over 256-byte ASCII buckets that computes bucket boundaries via counting sort and permutes elements directly into their target buckets using cyclic swap chains, reducing auxiliary memory from Θ(n) to O(d · b).

Suppose we must sort n unsigned W-bit integers (for example, W = 32 or W = 64). Grouping the W bits into d = ⌈W / r⌉ digits of r bits each defines radix b = 2^r, where each digit is extracted in two bitwise CPU instructions by right-shifting x by k · r bits and masking with 2^r − 1. Because each of the ⌈W / r⌉ passes performs Θ(n + 2^r) work, the total running time is:

T(n, W, r) = Θ( ( W / r ) · (n + 2^r) )

• If W ≤ log₂ n, choosing r = W executes a single counting-sort pass in Θ(n) time.
• If W > log₂ n, setting r = ⌊log₂ n⌋ balances the bucket table size 2^r ≤ n against the element count n, yielding Θ((W / log n) · n) total time. Whenever keys fit in a constant number of machine words (W = O(log n)), this simplifies to Θ(n) linear time.

In practical CPU cache hierarchies, engineers choose r = 8 (b = 256 buckets, 4 passes for 32-bit keys, 8 passes for 64-bit keys) or r = 11 (b = 2,048 buckets, 3 passes for 32-bit keys) so that both the histogram array C[0..b − 1] and the active write-combining cache lines fit comfortably inside the 32 KB L1 data cache, preventing translation lookaside buffer (TLB) thrashing during the scatter step.

Bijective Bit-Mask Transformations for Signed and Floating-Point Keys

Although LSD radix sort operates natively on unsigned binary integers, two branchless O(1) bitwise bijections extend it to signed two's-complement integers and IEEE-754 floating-point numbers:

1. Two's-Complement Signed Integers: In W-bit two's-complement representation, negative numbers have sign bit 1 (hexadecimal 0x80000000 to 0xFFFFFFFF) and positive numbers have sign bit 0 (0x00000000 to 0x7FFFFFFF). Flipping the most significant sign bit via bitwise XOR with 2^W−1 maps the minimum negative integer (−2^W−1) to 0 and the maximum positive integer (2^W−1 − 1) to 2^W − 1, preserving numerical order.
2. IEEE-754 Floating-Point Numbers (Michael Herf, 2001): An IEEE-754 float stores a 1-bit sign s, biased exponent e, and significand m such that positive floats already sort in ascending unsigned integer order (0x00000000 to 0x7F7FFFFF), whereas negative floats have sign bit 1 and sort in reversed magnitude order. Applying a conditional bitmask that flips only the sign bit if x ≥ 0 and flips all 32 bits (one's complement) if x < 0 maps all finite floats and ±∞ monotonically onto unsigned 32-bit integers.

Suffix Arrays and GPU Parallel Prefix-Scan Radix Sort

In bioinformatics, linear-time suffix array construction algorithms—such as the Kärkkäinen–Sanders DC3 skew algorithm—rely on 3-pass LSD radix sort over character triplets to sort 2/3 of a genome's suffixes in O(n) time when building the Burrows–Wheeler transform. On massively parallel graphics processing units (GPUs), Merrill and Grimshaw's OneSweep and NVIDIA CUB DeviceRadixSort decompose each LSD pass into warp-level parallel bit-scans and decoupled look-back prefix sums, sorting over 2 × 10⁹ 32-bit keys per second on a single GPU.

Why is stability mandatory in LSD radix sort but optional in MSD radix sort?

In LSD radix sort, pass k groups keys solely by their k-th digit while relying on pass k − 1 to have already ordered keys that tie on digit k; if pass k were unstable, it would scramble the lower-digit ordering established by previous passes. In MSD radix sort, once keys are partitioned into separate sub-arrays by their most significant digit k, subsequent passes operate strictly inside each sub-array and never move keys across higher-significance bucket boundaries.

When can comparison sorts like Quicksort or Introsort beat radix sort in practice?

Although radix sort performs Θ((W / r)n) operations versus Θ(n log n) for comparison sorts, a 64-bit LSD radix sort with r = 8 must read and scatter the entire n-element array between RAM and cache 8 full times. For small-to-moderate arrays (n ≤ 2,000) or 64-bit keys where only a few high-order bits differ, in-place cache-local Quicksort or Introsort can complete in fewer memory-bus transfers.

1. Seward, H. H. (1954). Information sorting in the application of electronic digital computers to business operations (Master's thesis, Report R-232). MIT Digital Computer Laboratory. https://doi.org/1721.1/61693
2. McIlroy, P. M., Bostic, K., & McIlroy, M. D. (1993). Engineering radix sort. Computing Systems, 6(1), 5–27. https://doi.org/10.5555/156668.156669
3. Kärkkäinen, J., Sanders, P., & Burkhardt, S. (2006). Linear work suffix array construction. Journal of the ACM, 53(6), 918–936. https://doi.org/10.1145/1217856.1217858
4. Merrill, D., & Grimshaw, A. (2011). High performance and scalable radix sorting: A case study of implementing dynamic parallelism for GPU computing. Parallel Processing Letters, 21(2), 245–272. https://doi.org/10.1142/S0129626411000187