SortingAlgorithmaka LSD radix sort, bucket-by-digit sort

Radix Sort

Sort integers digit by digit from least significant to most, using a stable counting sort per digit.

▶ VisualizePattern: HashingPractice (2)
Progress

Overview

Radix sort sorts fixed-width keys (integers, fixed-length strings, IEEE floats with a bit trick) by processing one digit at a time with a stable Counting Sort. The least-significant-digit (LSD) variant sorts by the last digit, then the second-to-last, and so on; after the final pass the array is fully sorted. Time is O(d · (n + b)) for d digits in base b — linear in n when d is constant.

Using base 256 (one byte per pass) sorts 32-bit integers in 4 passes and 64-bit in 8, and in practice beats Quick Sort on large arrays of integers by a wide margin. It is stable, not in-place (O(n + b) buffer), and not comparison-based, so the n log n lower bound does not apply. MSD radix sort (most significant first, recursive) is used for variable-length strings.

non-comparisonO(d·(n + b))stableinteger keyslinear timefixed-width keys

Intuition

A mental model before the formal terms.

Sorting a stack of 3-digit tickets: first deal them into 10 piles by the ones digit and restack in pile order; then deal by the tens digit and restack; then by the hundreds. Because each deal keeps ties in their previous order, the earlier (less significant) sorting is never undone — after the hundreds pass the stack is sorted.

How it works

  1. Pick a base b (10 for illustration, 256 for performance). Let d be the number of digits of the maximum key.
  2. For digit position p = 0, 1, …, d - 1 (least significant first): extract each key's digit (x / b^p) mod b.
  3. Run a stable counting sort on that digit: count, exclusive prefix sum, place in input order into a buffer.
  4. Swap the buffer and the array, then move to the next digit.
  5. Negative integers: offset keys, sort sign bit last, or partition negatives first and sort their magnitudes in reverse.

Why it works

Induction on passes: after processing digits 0..p, the array is sorted by the low p + 1 digits. The pass on digit p + 1 groups by that digit and, being stable, keeps elements with an equal digit p + 1 in their existing order — which is sorted by the lower digits. So the array is now sorted by the low p + 2 digits.

After all d passes the array is sorted by all digits, i.e. by value.

Each pass is a counting sort costing O(n + b); d passes give O(d · (n + b)).

Recognition

How to tell a problem wants this.

  • Sorting many integers (n ≥ 10^6) of bounded width where a linear-time sort is the intended optimization.
  • Keys are fixed-length strings, dates, IPs, or tuples of small integers (sort by the last field first, then the previous, using stable passes).
  • Range of values is large (so Counting Sort alone is impractical) but the number of digits is small.
  • Maximum gap between sorted adjacent elements in O(n) — the classic radix/bucket problem.
“have you seen this before” → Hashing“sum of subarray” → Prefix Sum

Interactive visualization

Play, step, change the input. ← → and space work too.

170
0
45
1
75
2
90
3
802
4
24
5
2
6
66
7
1/32The largest value 802 has 3 digit(s), so 3 pass(es) are needed. LSD radix sort sorts by ones, then tens, then hundreds, each time with a stable bucket distribution.
Element being bucketedDigit bucket receiving itSorted by digits so far
PseudocodeLearn Radix Sort →
1exp = 1
2while max(a) // exp > 0:
3  buckets = [[] for d in 0..9]
4  for x in a: buckets[(x // exp) % 10].append(x)   # stable
5  a = concat(buckets[0..9])
6  exp = exp * 10
Variables
exp1
digits3
Complexity
best O(d·(n + b))
avg O(d·(n + b))
worst O(d·(n + b))
space O(n + b)
Speed

Pseudocode

1exp = 1
2while max(a) / exp > 0:
3  count = [0] * b
4  for x in a: count[(x / exp) % b] += 1
5  pos = exclusive prefix sum of count
6  for x in a (in order): out[pos[(x / exp) % b]] = x; pos[...] += 1
7  a = out; exp *= b

Implementations

1def radix_sort(a: list[int]) -> list[int]:
2    """LSD radix sort for non-negative integers, base 256 (passes = bytes in max)."""
3    if not a:
4        return []
51 · Setup buffer and find the max key (bounds the number of passes)
6    src = a[:]
7    dst = [0] * len(a)
8    mx = max(a)
92 · One stable counting pass per byte, least significant first
10    shift = 0
11    while (mx >> shift) > 0:
123 · Histogram of the current byte
13        count = [0] * 257
14        for x in src:
15            count[((x >> shift) & 0xFF) + 1] += 1
164 · Prefix sums: count[d] = first output slot for digit d
17        for i in range(256):
18            count[i + 1] += count[i]
195 · Stable placement, then swap buffers
20        for x in src:
21            d = (x >> shift) & 0xFF
22            dst[count[d]] = x
23            count[d] += 1
24        src, dst = dst, src
25        shift += 8
26    return src
Walkthrough
  1. src = a[:] copies the input; dst is the ping-pong buffer.
  2. Python ints are arbitrary precision, so while (mx >> shift) > 0 does as many byte passes as the max key needs — 64-bit or 1000-bit keys work unchanged.
  3. (x >> shift) & 0xFF extracts the current byte; >> on non-negative ints is a clean logical shift.
  4. Placement writes dst[count[d]] then increments, keeping the pass stable.
  5. src, dst = dst, src swaps references in O(1).
Complexity (this implementation)
time O(w · (n + 256)), w = bytes in the max key · space O(n + 256)

Pure-Python loops make this slower than sorted() for almost any n; the algorithm is still worth knowing for fixed-width keys in NumPy (np.argsort(kind='stable') internally uses radix sort for small ints).

Language notes
  • Negative ints: >> is arithmetic (-1 >> 8 == -1), so shift keys by -min(a) first or split into negative/non-negative parts.
  • For strings of equal length use ord(s[d]) as the digit — MSD radix is the basis of trie-like sorts.
  • sorted(a) is TimSort: O(n log n), stable, in C; it is the practical answer unless you are in NumPy.
Common mistakes in this language
  • Passing negative numbers — the loop while (mx >> shift) > 0 still terminates but the digits are wrong; offset first.
  • Using base 10 with x // 10 ** d % 10 — correct, but ~3x more passes and slower division than bit ops.
  • Forgetting to return src (the swapped buffer) instead of a.
Language differences that matter here
  • Key width: C++ uint32_t keys fix 4 passes and make shifts well-defined; JS/TS bitwise ops truncate to 32 bits (>>> required for unsigned); Python ints are unbounded, so the pass count adapts to the largest key.
  • Negative keys: right shift is arithmetic in C++ (signed), JS >>, and Python — flip the sign bit (C++), use >>> (JS/TS, non-negatives only), or offset by min (Python).
  • Buffer swap: std::vector::swap (C++), reference reassignment (JS/TS/Python) — all O(1), so no per-pass copy.
  • Performance: C++ radix sort beats std::sort for large integer arrays; JS with Uint32Array beats sort(); pure-Python radix sort is slower than C-implemented sorted() (TimSort) at any size.
  • No comparisons happen, so the JS lexicographic sort() pitfall does not apply — but keys must be integers in every language.

Complexity

Best
O(d·(n + b))
Average
O(d·(n + b))
Worst
O(d·(n + b))
Space
O(n + b)

d = digits per key, b = base. For 32-bit keys with b = 256: 4 passes, effectively O(n). Stable, not in-place, not adaptive.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Large arrays of fixed-width integers or fixed-length strings where O(n log n) comparisons are the bottleneck.
  • Sorting by multiple fields: stable passes from least to most significant field.
  • GPU / SIMD / parallel sorting — radix sort parallelizes far better than comparison sorts.
  • Suffix array construction and other string algorithms that repeatedly sort tuples of small integers.
Avoid it when
  • Variable-length or arbitrary-comparator keys (use a comparison sort or MSD radix for strings).
  • Small n — the per-pass overhead and buffer make Insertion Sort or Quick Sort faster.
  • Keys with many digits relative to log n (e.g. 64-bit keys with n = 1000): d passes cost more than log n comparisons.
  • In-place requirement or memory-constrained environments.

Alternatives

Counting SortBucket SortQuick SortMerge Sort

Common mistakes

  • Using an unstable sort per digit — the passes then undo each other.
  • Handling negative numbers by feeding two's complement bits straight in; the sign bit sorts negatives after positives. Flip the sign bit (or offset) first.
  • Processing digits most-significant first with the LSD algorithm.
  • Recomputing max or allocating the count array in a way that makes the constant factor larger than a comparison sort.

Interview patterns

  • Maximum gap in O(n): radix sort or bucket the values then scan adjacent buckets.
  • Sort a list of fixed-length strings / license plates in linear time.
  • Explain when radix sort beats std::sort and why the n log n lower bound does not apply.
  • Sort (x, y) pairs by x then y using two stable counting passes.
Interview questions on this
Mock interviews

Example problems

Sort Colors (Dutch National Flag)mediumKth Largest Element in an Arraymedium