Radix / Bucket SortRadix and bucket sort

01Why it exists

Reach for it when you see:Integers or fixed-length strings, a range too wide to count directly, a fixed number of digits (phone numbers, dates, IP addresses, 32-bit IDs), needing to beat O(n log n), uniformly distributed floats, bucketing, maximum gap.

02The core idea

Counting sort cannot allocate its count array once the value range k gets large. Radix sort splits one wide key into d small digits, each with only b possible values (b = 10 in decimal, b = 256 for a byte), then works from the lowest digit up, running a stable counting sort on that one digit across the whole sequence. After d passes the sequence is sorted. That is LSD (least significant digit) radix sort. Going the other way — cutting into b buckets by the highest digit and recursively sorting each bucket — is MSD, which suits strings of differing length but is harder to implement.

Here is why it starts at the lowest digit and why every pass has to be stable. Argue by induction on the claim "after pass j, the sequence is sorted by its lowest j digits." Pass j+1 reorders by digit j+1: two elements that differ on this digit are put in the right order by this very pass, and two elements that agree on it keep the order the previous pass left them in, because the sort is stable — and that previous order was sorted by the lowest j digits, so the pair is now sorted by the lowest j+1 digits too. Drop stability and ties on this digit scramble the previous pass's work, which breaks the whole argument. Running the same thing from the high digit downwards is simply wrong, because the final pass looks at the lowest digit and would bury the ordering the high digits established.

Complexity: each pass is one O(n + b) counting sort and there are d of them, so the time is O(d·(n + b)), regardless of how the data happens to be arranged. The space is the scratch array plus the count array, O(n + b). The digit count and the base have to be chosen together: a 32-bit integer needs only 4 passes at b = 256, with a tiny 256-slot count array each time, while b = 65536 needs just 2 passes but a count array too big for the cache, which makes the constant worse instead. When d is a constant — fixed-width integers, fixed-length strings — radix sort is linear time, and at n = one hundred million, 4 passes against log₂ n ≈ 27 levels is a visible gap. It only applies to keys you can split into digits: negative numbers need their sign bit flipped or the whole range shifted first, and floats need an order-preserving bit representation.

Bucket sort is the other route. When the data is roughly uniform floats in [0, 1), open n buckets, drop x into bucket ⌊x·n⌋, and each bucket holds an expected O(1) elements; sort inside each with insertion sort and concatenate the buckets in order for expected O(n). Its premise is the distribution, not the digit count: if everything piles into one bucket it degrades to whatever the inner sort costs (O(n²) for insertion sort), so it is unreliable on input whose distribution you do not know. The usual traps: x = 1.0 computes bucket n and runs off the end, so clamp it to n − 1; one LSD pass quietly using a sort that is not stable; and digits that are not padded out (strings of different lengths must be padded to a common length, or handled with MSD instead). How this connects to the previous lesson: each pass of radix sort is a stable counting sort. The next lesson explains why both of them can beat n log n — neither one compares elements at all.

03The algorithm

1. 1Pick the base and the digit count: decimal data means b = 10 and d = the number of digits in the largest value; a 32-bit integer means b = 256 and d = 4; a fixed-length string uses one digit per character.
2. 2Start at the lowest digit. On pass j, extract that digit from each element, for example x // b^j % b or (x >> 8j) & 0xFF.
3. 3Run a stable counting sort on that digit: count how many elements have each value, prefix-sum the counts into the starting offset of each run, then copy the elements into a scratch array in order.
4. 4The scratch array becomes the input to the next pass. Move up one digit, and after d passes the whole sequence is sorted.
5. 5For uniformly distributed floats, switch to bucket sort: open n buckets, drop x into bucket min(⌊x·n⌋, n−1), sort inside each bucket, and concatenate them in order.

04Interactive demo

Nine two-digit numbers. The tens digits of the first eight are the shared array [5, 2, 9, 1, 7, 3, 8, 4], the units digits are deliberately scrambled, and one extra value, 24, makes the tens digit 2 appear twice. The first pass buckets by units digit into buckets 0-9 and collects them back in order; the second pass does the same by tens digit. The underline marks the digit this pass is reading, blue is the element being bucketed right now, grey is everything already in a bucket, and green is the sequence collected back. Watch bucket 2 on the second pass: 24 comes before 29 because the first pass already put 24 ahead of 29 by units digit, and this pass stably preserves that order.

05Code

The Python side has decimal LSD radix sort (change the base argument and it reads one byte per pass), a version for fixed-length strings, and bucket sort. The C++ side is the shape you meet in practice: 8 bits per pass over a 32-bit integer, always 4 passes, using a count array to work out where each run starts before copying the elements across; bucket sort follows. Every pass in both languages is stable, which is what makes radix sort correct in the first place.

# LSD radix sort: non-negative integers. Lowest digit first, each pass a stable counting sort on one digit.
def radix_sort(a, base=10):
    if not a:
        return a
    exp, biggest = 1, max(a)
    while biggest // exp > 0:                # there is still a higher digit
        count = [0] * base
        for x in a:
            count[x // exp % base] += 1
        for d in range(1, base):
            count[d] += count[d - 1]
        out = [0] * len(a)
        for x in reversed(a):                # back to front: ties on this digit keep the last pass's order
            d = x // exp % base
            count[d] -= 1
            out[count[d]] = x
        a, exp = out, exp * base
    return a


# Fixed-length strings (phone numbers, dates): walk back from the last character, bucketing by character
def radix_sort_strings(words):
    for pos in range(len(words[0]) - 1, -1, -1):
        buckets = [[] for _ in range(128)]   # ASCII
        for w in words:
            buckets[ord(w[pos])].append(w)   # appended in the current order, so the pass stays stable
        words = [w for b in buckets for w in b]
    return words


# Bucket sort: roughly uniform floats in [0, 1). With n buckets, each one holds O(1) items on average.
def bucket_sort(xs):
    n = len(xs)
    buckets = [[] for _ in range(n)]
    for x in xs:
        buckets[min(int(x * n), n - 1)].append(x)   # bucket i covers [i/n, (i+1)/n)
    return [x for b in buckets for x in sorted(b)]  # each bucket is tiny; sort it, then concatenate


if __name__ == "__main__":
    print(radix_sort([52, 29, 91, 17, 73, 38, 84, 45, 24]))   # [17, 24, 29, 38, 45, 52, 73, 84, 91]
    print(radix_sort([170, 45, 75, 90, 802, 24, 2, 66], base=256))
    # [2, 24, 45, 66, 75, 90, 170, 802] (base 256: one byte per pass, so two passes finish it)
    print(radix_sort_strings(["0912", "0203", "0911", "0122", "0203"]))
    # ['0122', '0203', '0203', '0911', '0912']
    print(bucket_sort([0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68]))
    # [0.12, 0.17, 0.21, 0.23, 0.26, 0.39, 0.68, 0.72, 0.78, 0.94]

06Practice

• LeetCode 1356Sort Integers by The Number of 1 Bits (values stay under 10⁴, so the bit count is only 0-13: bucket on it)Easy
• LeetCode 1502Can Make Arithmetic Progression From Sequence (once you know the common difference, each value's slot is a direct calculation)Easy
• LeetCode 451Sort Characters By Frequency (the frequency is the bucket index)Medium
• LeetCode 2343Query Kth Smallest Trimmed Number (radix sort on fixed-length strings)Medium
• LeetCode 220Contains Duplicate III (buckets of width valueDiff + 1)Hard