Radix Sort

Overview

Radix Sort is a non-comparison-based sorting algorithm that sorts numbers by processing individual digits. It works by sorting the numbers digit by digit, starting from the least significant digit (LSD) or most significant digit (MSD).

Unlike comparison-based sorting algorithms, Radix Sort doesn't compare elements directly. Instead, it uses the digits of the numbers to distribute them into buckets, making it potentially faster than comparison-based algorithms for certain types of data.

This is the algorithm's central peculiarity: radix sort escapes the Ω(n log n) lower bound that every comparison-based sort is bound by. The lower bound is not violated, it applies only to algorithms whose only operation on keys is comparing pairs. Radix sort does something different: it looks at the internal structure of each key, one digit at a time. If your keys have a fixed digit width, 32-bit integers, 8-byte doubles, IP addresses, timestamps, radix sort runs in linear time. On the right data, it is the fastest sort ever devised.

Historical Origin: The Card-Sorting Machine

Radix sort predates electronic computers entirely. It was implemented in mechanical form by Herman Hollerith in 1887 as part of the punched-card tabulating machine he built to process the 1890 US census, which became the founding technology of what would eventually be renamed IBM. Hollerith's tabulator sorted stacks of punched cards by mechanically routing each card into one of ten output bins based on the value of a specified column, then merging the bins back into a single stack in order. Doing this repeatedly, one column at a time from the least significant to the most significant digit of the numeric field, produced a fully sorted deck.

That mechanical algorithm is exactly LSD radix sort, invented and deployed 60 years before the first stored-program computer. The 1890 US census was processed in six weeks, a task that had taken seven years by hand for the previous census. Radix sort's competitive advantage over comparison-based sorting is, in a very real sense, older than the field of computer science itself.

The transfer to electronic computers happened almost immediately once storage allowed it, and the algorithm has had continuous life in the literature since. Modern high-performance implementations, on multi-core CPUs, on GPUs, on custom database sorting hardware, are typically variants of radix sort. NVIDIA's CUB library, PyTorch's tensor sorting, and the sort primitives used inside major database columnar engines are all radix-sort based. Hollerith's basic idea has never gone out of fashion.

LSD vs MSD Radix Sort

Radix sort has two major flavours, distinguished by which digit they process first.

LSD (Least Significant Digit) radix sort processes digits from right to left, using a stable inner sort at each pass. The stability is essential, when we sort by digit d, keys that agree on digit d must keep the order established by the previous passes on digits 1 through d−1. This is the version implemented in most textbooks (and in the code above) because the analysis is cleanest and the implementation is the simplest. It requires knowing the number of digits in advance, and it processes every element on every pass regardless of whether digits above the current one have already established the order.

MSD (Most Significant Digit) radix sort processes digits from left to right, recursing into each bucket. Once we sort by the top digit into 10 (or 256, or however many) buckets, keys in different buckets are already in the correct relative order and never need to be compared again, recursion happens only within each bucket. This makes MSD radix sort particularly good for variable-length keys, because once a key is shorter than the current recursion depth it can be output immediately without further processing. It is also the natural way to sort strings: process them left to right, character by character, exactly as a human would sort them alphabetically.

The choice between LSD and MSD depends on the data:

Fixed-width numeric data, LSD is simpler and typically faster
Variable-length strings, MSD is more natural and avoids wasted work on already-sorted prefixes
Very large data with distinct prefixes, MSD parallelises trivially, since different top-level buckets can be sorted independently on different threads
Data with many duplicate values, three-way variants of MSD (Bentley–Sedgewick multikey quicksort) beat both plain LSD and plain MSD

Counting Sort: The Building Block

Radix sort is not a standalone algorithm so much as a scheme for applying a simpler sort, counting sort, multiple times. Counting sort itself is worth understanding: given n integers in a small range 0..k, counting sort produces a sorted output in O(n + k) time using O(n + k) space. It works by counting how many times each value appears (one pass), computing a cumulative distribution (which tells you where each value should start in the output), and then placing each input element into its slot (a second pass).

Counting sort is optimal when the value range is small compared to n. Sorting a million grades on a 0–100 scale takes O(1 000 000 + 100) ≈ 1 000 100 operations, which is faster than any O(n log n) sort by a factor of 20. When k is close to n², counting sort loses to comparison-based sorts because its space and initialisation costs dominate.

Radix sort's insight is that you can turn a small-range counting sort into a general integer sort by applying it to one digit at a time. If your integers are 32 bits, you can sort them by radix 256 in exactly 4 passes of counting sort, each on a range of 256. That is O(n) work per pass and 4 passes total, genuinely O(n) time, regardless of how large your integers are, as long as their bit width is bounded.

Modern Variants

American Flag Sort

Peter McIlroy's in-place MSD radix sort (published as "Engineering Radix Sort" in Computing Systems, 1993). The name comes from the way it looks when sorting strings alphabetically: the buckets appear as coloured bands in the output. American flag sort avoids the O(n) auxiliary array that plain LSD radix sort needs, at the cost of more complex bookkeeping. It is used in the BSD C library's qsort for string sorting and in several high-performance database engines.

Burstsort

Ranjan Sinha and Justin Zobel's 2003 algorithm, designed for sorting large volumes of strings. Burstsort maintains a trie in which each leaf holds a small "container" of strings; when a container fills, it is "burst" into a deeper subtree. This gives cache-friendly memory access patterns that plain MSD radix sort lacks, and burstsort is one of the fastest known string sorting algorithms in practice, often 2–5x faster than quicksort on real datasets of strings.

Radix Sort on Floating-Point Numbers

A common misconception is that radix sort cannot handle floating-point values. In fact, IEEE 754 doubles can be sorted by radix sort with a small bit-manipulation trick: for positive values, the binary representation happens to sort in the same order as the numeric value; for negative values, the sign bit is flipped and the mantissa is reversed. A pair of XOR-and-shift operations converts any IEEE 754 double to an unsigned 64-bit integer whose integer sort order matches the original double's numeric order. NVIDIA's CUB library and Google's cityhash both use this trick to sort floats via radix sort on GPUs.

Parallel and GPU Radix Sort

Radix sort is one of the easiest sorts to parallelise: within each digit pass, the counting and distribution steps can be split across threads that each process a chunk of the input, with a small serial reduction to combine the local counts. On GPUs, this makes radix sort dramatically faster than any comparison-based sort, a modern GPU sorts a billion 32-bit keys per second, which no comparison sort has ever approached.

Common Misconceptions

"Radix sort violates the Ω(n log n) lower bound for sorting." No, the lower bound applies only to comparison-based sorts. Radix sort does not compare pairs of keys; it looks at the internal structure of each key. Different model, different bound.
"Radix sort only works for integers." It works for any keys with a fixed-length representation over a small alphabet: integers, fixed-length strings, IPv4 addresses, timestamps, and (with the bit trick above) IEEE 754 floats. It does not naturally handle arbitrary user-defined types with only a comparison operator.
"Radix sort is O(n) so it is always faster than O(n log n) sorts." Hidden in the constant is a factor of the key width w. For 32-bit integers, radix sort with radix 256 is 4n work; a good quicksort is roughly 20n at n = 1000. Radix sort wins on large data but not always at small n, and the memory-access pattern can be less cache-friendly than a comparison sort.
"You need a large radix for radix sort to be fast." Choosing the radix is a tuning problem. Larger radix = fewer passes but more cache pressure on the count array. In practice radix 256 (one byte per pass) is a sweet spot on modern CPUs; GPUs often use radix 4 or 8 for better parallelism.

How It Works

The algorithm works by:

Finding the maximum number to determine the number of digits
For each digit position (from least to most significant):
Distribute numbers into buckets based on the current digit (0-9)
Collect numbers from buckets in order
Repeat for the next digit position

The algorithm uses a stable sorting algorithm (typically counting sort) as a subroutine for each digit position.

Algorithm


RadixSort(arr):
    max_val = find maximum value in arr
    exp = 1  // Start with least significant digit
    
    while max_val / exp > 0:
        counting_sort(arr, exp)
        exp *= 10  // Move to next digit

CountingSort(arr, exp):
    n = length of arr
    output = array of size n
    count = array of size 10, initialized to 0
    
    // Count occurrences of each digit
    for i = 0 to n - 1:
        index = (arr[i] / exp) % 10
        count[index]++
    
    // Change count to position
    for i = 1 to 9:
        count[i] += count[i - 1]
    
    // Build output array
    for i = n - 1 down to 0:
        index = (arr[i] / exp) % 10
        output[count[index] - 1] = arr[i]
        count[index]--
    
    // Copy output to arr
    for i = 0 to n - 1:
        arr[i] = output[i]

Implementation


def counting_sort(arr, exp):
    """Counting sort as subroutine for radix sort"""
    n = len(arr)
    output = [0] * n
    count = [0] * 10
    
    # Count occurrences of each digit
    for i in range(n):
        index = (arr[i] // exp) % 10
        count[index] += 1
    
    # Change count to position
    for i in range(1, 10):
        count[i] += count[i - 1]
    
    # Build output array
    for i in range(n - 1, -1, -1):
        index = (arr[i] // exp) % 10
        output[count[index] - 1] = arr[i]
        count[index] -= 1
    
    # Copy output to arr
    for i in range(n):
        arr[i] = output[i]

def radix_sort(arr):
    """LSD radix sort for non-negative integers."""
    if not arr:
        return arr

    # Find maximum number to know number of digits
    max_val = max(arr)

    # Do counting sort for every digit
    exp = 1
    while max_val // exp > 0:
        counting_sort(arr, exp)
        exp *= 10

    return arr


def radix_sort_signed(arr):
    """Handles negative values, which the version above silently corrupts.

    Python's floor semantics make (-5 // 1) % 10 evaluate to 5, so negatives get
    bucketed as though positive and no error is raised - radix_sort([-5, 3])
    quietly returns [3, -5]. Split by sign, sort magnitudes, then reverse the
    negative half and put it in front.
    """
    if not arr:
        return arr

    negatives = [-x for x in arr if x < 0]
    positives = [x for x in arr if x >= 0]

    if negatives:
        radix_sort(negatives)
        negatives = [-x for x in reversed(negatives)]
    if positives:
        radix_sort(positives)

    arr[:] = negatives + positives
    return arr

Complexity Analysis

Time Complexity:
- Best/Average/Worst Case: O(d × (n + k)) where d is number of digits, n is array size, k is range (10 for decimal digits)
- For integers with fixed width (e.g., 32-bit): O(n), since d is a constant. Worth a caveat though, if the n keys must be distinct, you need at least d ≥ log_k n digits to tell them apart, so the "linear" bound quietly hides a log n factor. Radix sort does not actually escape the comparison-sort lower bound so much as sidestep the model it applies to.
- For variable-width integers: O(n × d) where d is the number of digits in the maximum number
Space Complexity: O(n + k) - for output array and count array

Radix Sort's performance depends on the number of digits. For numbers with a fixed number of digits (like 32-bit integers), it can be O(n), making it very efficient for large datasets of integers.

Characteristics

Stable: Yes - when using stable counting sort
In-place: No - requires O(n) extra space
Adaptive: No - always performs the same operations
Online: No - requires the entire array
Non-comparison: Yes - doesn't compare elements directly

When to Use Radix Sort

Radix Sort is ideal when:

Sorting integers or strings with fixed-length keys
Keys have a limited range of values
You need stable sorting
Sorting large datasets of integers
When the number of digits is small compared to the array size

Not suitable for:

Small arrays, the constant factors lose to a good comparison sort
When memory is severely limited (it is not in-place)
Keys with no natural digit decomposition

Two Common Misconceptions

"Radix sort can't handle variable-length keys." LSD radix sort cannot, but MSD radix sort handles them naturally, and sorting variable-length strings is its primary use. MSD starts from the most significant digit, partitions into buckets, and recurses within each bucket; a key that runs out of characters simply sorts first. Unlike LSD it does not need to examine every character of every key, so it often finishes after inspecting only a short distinguishing prefix. American flag sort is an in-place MSD variant, and burstsort is a cache-efficient refinement; both are used to sort large string collections faster than comparison sorts can.

"Radix sort can't handle floats." It can, with a bit-level trick. IEEE-754 floats are ordered correctly as sign-magnitude integers already, so flipping the sign bit for positives and inverting all bits for negatives yields unsigned integers whose ordering matches the float ordering exactly. Sort those, then undo the transform.

Example

Sorting [170, 45, 75, 90, 2, 802, 24, 66]:

Initial: [170, 45, 75, 90, 2, 802, 24, 66]

Pass 1 (ones place):
  [170, 90, 2, 802, 24, 45, 75, 66]

Pass 2 (tens place):
  [2, 802, 24, 45, 66, 170, 75, 90]

Pass 3 (hundreds place):
  [2, 24, 45, 66, 75, 90, 170, 802]

Sorted: [2, 24, 45, 66, 75, 90, 170, 802]

Related Algorithms

Explore other sorting algorithms:

Heap Sort - In-place O(n log n) sort
Merge Sort - Stable divide-and-conquer
Tim Sort - Hybrid sorting algorithm
Back to Sorting Algorithms Overview