Radix Sort Explained: LSD, MSD, Bases and Negative Numbers

Radix sort is the sort that never compares two elements. It reads each key as a sequence of digits and distributes the keys into buckets one digit position at a time. Done in the right order with the right kind of pass, a handful of distributions leaves the whole list sorted. The surprising part, starting from the least important digit, is the part worth understanding.

The problem it solves

Comparison sorts need about n log n comparisons in the worst case; no amount of cleverness gets under that while the only question you ask is "which of these two is smaller?". Radix sort asks a different question, "what is this key's digit at position d?", and the lower bound does not apply to it.

The building block, a stable counting pass, and the case for small ranges are covered in counting sort vs radix sort. Here the focus is radix sort itself: the order of the passes, how to choose the digit size, what to do with negative numbers, and the most-significant-first variant that sorts strings.

The intuition

LSD (least significant digit first). Distribute every key into buckets 0 to 9 by its last digit, then collect the buckets in order. Repeat with the next digit to the left, and so on. After the pass on digit d, the keys are sorted by their last d digits. A later pass sorts by a more important digit; when two keys tie on it, they must keep the order the earlier passes gave them. That is the job of stability: appending to the end of a bucket and collecting front to back never reorders ties.

The base is a dial. A "digit" does not have to be decimal. With 32-bit keys and 8 bits per digit there are 4 passes of 256 buckets; with 16 bits, 2 passes of 65,536 buckets. Fewer passes mean more buckets to allocate and scan per pass. Bytes are a common middle ground.

Negative numbers break the plain digit extraction, because a negative key has no sensible last digit. For fixed-width integers, add a bias that shifts the range to start at zero, for 32 bits that is 2**31, which is the same as flipping the sign bit. Order is preserved, so sort the biased keys and subtract the bias again.

MSD (most significant digit first) goes the other way: bucket on the first character, then sort each bucket separately and recursively on the next character. It suits variable-length strings, and it can stop early: a bucket of one word needs no more passes, so MSD often reads only the distinguishing prefix of each key. Its cost is recursion and many small buckets.

Watch it run

The animation sorts five two-digit numbers, 72, 38, 25, 31 and 58. Radix sort never compares two numbers: it sorts by one digit at a time, starting from the right. Pass 1 reads the ones digit of every value, and that digit is the bucket it falls into. The buckets are collected back in order, 0 to 9, and because the pass is stable, ties keep the order they arrived in: 31, 72, 25, 38, 58, with zero comparisons. Pass 2 reads the tens digit and collects again: 25, 31, 38, 58, 72. Look at 31 and 38. They tied on the tens digit, and their order came from the previous pass, which is exactly why the walk starts on the right. Two passes for two-digit numbers, linear in the number of values per pass, and not one value was ever weighed against another.

The code

The lesson's LSD sort with a guard for the empty list and an optional trace, run on the animation's input:

def radix_sort(nums, base=10, trace=False):
    """LSD radix sort for non-negative integers, printing each pass if asked."""
    if not nums:
        return []                                  # max([]) would raise
    place = 1
    while place <= max(nums):
        buckets = [[] for _ in range(base)]
        for x in nums:
            buckets[x // place % base].append(x)   # appending keeps ties in order
        nums = [x for b in buckets for x in b]
        if trace:
            print(place, nums)
        place *= base
    return nums

radix_sort([72, 38, 25, 31, 58], trace=True)
# 1 [31, 72, 25, 38, 58]
# 10 [25, 31, 38, 58, 72]

Signed 32-bit integers: bias into the non-negative range, then a fixed number of passes set by the bits per digit. The table of passes and buckets is the base dial in numbers:

def radix_sort_int32(nums, bits=8):
    """Signed 32-bit integers: bias into 0..2**32 - 1, then bits per pass."""
    keys = [x + 2**31 for x in nums]               # same order, no negatives left
    mask, passes = (1 << bits) - 1, 0
    for shift in range(0, 32, bits):
        buckets = [[] for _ in range(1 << bits)]
        for k in keys:
            buckets[(k >> shift) & mask].append(k)
        keys = [k for b in buckets for k in b]
        passes += 1
    return [k - 2**31 for k in keys], passes

print(radix_sort_int32([5, -3, 2**31 - 1, 0, -2**31, -3]))
# ([-2147483648, -3, -3, 0, 5, 2147483647], 4)
for bits in (1, 4, 8, 16):
    print(bits, "bits:", 32 // bits, "passes,", 1 << bits, "buckets each")
# 1 bits: 32 passes, 2 buckets each
# 4 bits: 8 passes, 16 buckets each
# 8 bits: 4 passes, 256 buckets each
# 16 bits: 2 passes, 65536 buckets each

MSD for ASCII strings. A word that has ended sorts before every longer word sharing its prefix, and a counter records how many characters were actually read:

def msd_sort(words, d=0, reads=None):
    """MSD radix sort for ASCII strings: bucket on character d, then recurse per bucket."""
    if len(words) <= 1:
        return words
    ended = [w for w in words if len(w) == d]      # a shorter word sorts first
    buckets = [[] for _ in range(128)]
    for w in words:
        if len(w) > d:
            if reads is not None:
                reads[0] += 1
            buckets[ord(w[d])].append(w)
    out = ended
    for b in buckets:                              # bucket order is character order
        out += msd_sort(b, d + 1, reads)
    return out

words = ["radix", "rad", "sort", "stable", "bucket", "bin", "byte", "sorted"]
reads = [0]
print(msd_sort(words, reads=reads))
# ['bin', 'bucket', 'byte', 'rad', 'radix', 'sort', 'sorted', 'stable']
print(reads[0], sum(map(len, words)))
# 24 37

Twenty-four character reads sorted 37 characters of input: once a bucket holds one word, its remaining characters are never looked at. Finally, all three sorts are checked against Python's sorted on 1,000 seeded random inputs, with duplicates forced into the signed lists:

import random

rng = random.Random(34)
ok = True
for _ in range(1000):
    small = [rng.randint(0, rng.choice([9, 999, 10**6])) for _ in range(rng.randint(0, 40))]
    ok &= radix_sort(small) == sorted(small) == radix_sort(small, base=256)
    signed = [rng.randint(-2**31, 2**31 - 1) for _ in range(rng.randint(0, 40))]
    signed += rng.sample(signed, min(3, len(signed)))     # force some duplicates
    for bits in (1, 4, 8):                                # 16 works too, but slowly here
        ok &= radix_sort_int32(signed, bits)[0] == sorted(signed)
    ws = ["".join(rng.choice("abc") for _ in range(rng.randint(0, 5))) for _ in range(rng.randint(0, 30))]
    ok &= msd_sort(ws) == sorted(ws)
print(ok)                                                 # True

The complexity

• LSD: O(d · (n + b)) time for d digit positions in base b, and O(n + b) extra space for the buckets.
• Fixed-width keys: d is a constant, 4 byte passes for 32-bit integers, so the sort is linear in n. The Big-O cheat sheet lists it beside the comparison sorts.
• MSD: at most the total length of the keys in character reads, often far less, plus a bucket array per recursive call.

Where it goes wrong

• An unstable pass. Every pass after the first destroys the order the earlier ones built.
• Going left to right with LSD's method. Sorting the whole list by the first digit, then the whole list by the second, does not work; MSD must recurse into each bucket.
• Negative numbers. x // place % 10 on a negative value gives digits of the wrong meaning; bias the keys first.
• Huge buckets per pass. 16-bit digits allocate 65,536 buckets each pass; on small inputs that dominates the run time, as the check above avoided.
• Short lists. Constant factors favour a comparison sort until n is large.

When it shows up in interviews

As "sort these in linear time", "sort a million 32-bit integers" or "how can a sort beat n log n?". Follow-ups ask why stability matters, how to handle negatives, how the base trades passes for memory, and how to sort strings, which leads to MSD.

How to say it in an interview

"Radix sort distributes keys into buckets by one digit at a time instead of comparing them. LSD starts at the least significant digit and needs each pass to be stable, so ties on a higher digit keep the order the lower digits established. That costs O(d · (n + b)), and with fixed-width keys d is constant, so it is linear. The base trades passes against buckets: bytes give four passes for 32-bit integers. Negatives get a bias, which is flipping the sign bit. For variable-length strings I would use MSD, which recurses per bucket and stops once a bucket has one key."