Sort by the last digit, then the next, then the next. No two values are ever compared — which is how radix sort slips past the O(n log n) barrier that binds every comparison sort.
Controls
values8
for d in digits(least→most):
buckets = [[] for _ in range(10)]
for x in a:
buckets[digit(x,d)].append(x)
a = concat(buckets) # stable
Digit Passes
step 0
Current array
Buckets 0–9
Insight
Radix sort never compares two values. It distributes by digit and relies on the bucketing being stable — equal keys keep their previous relative order.
pass0
digit place–
comparisons0
operations0
Complexity
TimeO(d·n)
SpaceO(n+k)
Comparisons0
Radix Sort
Sorting without ever asking which of two values is bigger.
The idea in brief
Radix sort processes numbers one digit at a time, distributing them into buckets by that digit and collecting them back. Repeat for every digit position — least significant first — and the array emerges sorted, with zero comparisons.
Why Stability Is Non-Negotiable
This is the crux. When sorting by the tens digit, two numbers with the same tens digit must retain the order they got from the units pass — otherwise that earlier work is destroyed.
A stable bucketing preserves relative order of equal keys, so each pass refines the previous one instead of undoing it. Watch numbers entering a bucket: they always append to the end, never jump the queue. Swap in an unstable bucketing and radix sort simply stops working.
Least Significant Digit First
It feels backwards to start with the last digit, but it is what makes stability sufficient. After the units pass, the array is sorted by units. After the tens pass, it is sorted by tens with units breaking ties — because stability preserved them. After the hundreds pass, fully sorted.
Step through and check the array after each pass: it is correctly sorted by all digits processed so far.
Beating the O(n log n) Barrier
Any sort that works by comparing elements needs at least O(n log n) comparisons — that is a proven lower bound, not an engineering limitation. Merge sort and heap sort sit exactly on it.
Radix sort escapes because it never compares. Its cost is O(d · n) for d digits, which is linear in n when d is fixed. There is no contradiction: the lower bound only constrains comparison sorts.
The Catch
It needs O(n + k) extra space for buckets — it does not sort in place.
It only works on keys decomposable into digits: integers, fixed-length strings, dates. Arbitrary objects with a custom comparator are out.
The d factor matters. For 64-bit integers d can be large enough that O(n log n) wins in practice.
Cache behaviour is poor — scattering into buckets jumps around memory.
Its sweet spot is large volumes of fixed-width keys, which is why it appears in database index construction and older card-sorting machinery — literally where the algorithm came from.
Sorting digit by digit
Radix sort avoids comparisons entirely. It sorts numbers by processing one digit at a time, using a stable counting sort for each pass.
Sorting [170, 45, 75, 90, 802, 24, 2, 66] by units, then tens, then hundreds:
Pass
Result
By units
[170, 90, 802, 2, 24, 45, 75, 66]
By tens
[802, 2, 24, 45, 66, 170, 75, 90]
By hundreds
[2, 24, 45, 66, 75, 90, 170, 802]
Three passes, and the array is sorted. No two elements were ever compared with each other.
def radix_sort(arr):
if not arr:
return arr
max_val = max(arr)
exp = 1
while max_val // exp > 0:
arr = counting_sort_by_digit(arr, exp)
exp *= 10
return arr
def counting_sort_by_digit(arr, exp):
counts = [0] * 10
for x in arr:
counts[(x // exp) % 10] += 1
for i in range(1, 10):
counts[i] += counts[i - 1] # cumulative positions
out = [0] * len(arr)
for x in reversed(arr): # backwards: preserves stability
d = (x // exp) % 10
counts[d] -= 1
out[counts[d]] = x
return out
Stability is not optional
The reversed(arr) on the second-to-last line is what makes the whole algorithm work.
Each pass must preserve the relative order established by the previous passes. If sorting by tens reordered two numbers that were already correctly ordered by units, the units pass would be wasted.
So radix sort requires a stable inner sort, and that is why counting sort's cumulative-position form — iterating the input backwards — is the version used. Using an unstable inner sort produces a wrong answer that looks nearly sorted, which is a confusing failure.
This is the clearest practical demonstration of why stability is a property worth caring about rather than a technicality.
Complexity, and the choice of base
O(d × (n + k)) where d = digits, k = base
The base is a tuning parameter, and the trade is direct: a larger base means fewer passes and a bigger count array.
Base
Passes for 32-bit integers
Count array
10
10
10
16
8
16
256
4
256
65,536
2
65,536
Base 256 — one byte per pass — is the usual choice for integers. Four passes, a 256-entry array, and the digit extraction is a bit shift and mask rather than division, which is considerably faster.
The complexity is linear in n for fixed-width keys, which beats the O(n log n) comparison lower bound. That is not a contradiction: the bound applies only to comparison-based sorts, and radix sort never compares.
Sort
Complexity
Requires
Radix
O(d(n+k))
Fixed-width integer-like keys
Counting
O(n+k)
Small integer range
Comparison sorts
Ω(n log n)
Only a comparison function
What happens when the inner sort is not stable
The article says stability is non-negotiable for radix sort. That is a claim you can break on purpose: run the same algorithm with a stable inner pass and an unstable one, and watch the second produce a list that is simply wrong.
example_01.pyPython
def digit(x, place):
return (x // place) % 10
def radix(a, stable=True):
a = a[:]
place = 1
passes = 0
while place <= max(a):
buckets = [[] for _ in range(10)]
for x in a:
buckets[digit(x, place)].append(x)
if not stable:
# An unstable inner sort keeps the same DIGIT grouping but
# loses the order within each bucket. Reversing each bucket is
# one concrete way to be unstable.
buckets = [list(reversed(b)) for b in buckets]
a = [x for b in buckets for x in b]
passes += 1
place *= 10
return a, passes
data = [170, 45, 75, 90, 802, 24, 2, 66]
print("input: ", data)
ok, passes = radix(data, stable=True)
bad, _ = radix(data, stable=False)
print("stable inner: ", ok, " sorted:", ok == sorted(data))
print("unstable inner: ", bad, " sorted:", bad == sorted(data))
print("passes:", passes, "(one per digit of the largest number)")
# The unstable run visits the same buckets in the same order and still
# produces the wrong answer. The reason is that pass 2 sorts by the tens
# digit and assumes the ones digit is ALREADY in order within each group.
# Stability is what carries that earlier work forward; without it, every
# pass destroys the one before and only the final digit ends up sorted.
#
# Watch it happen one pass at a time.
def trace(a, stable):
place = 1
while place <= max(a):
buckets = [[] for _ in range(10)]
for x in a:
buckets[digit(x, place)].append(x)
if not stable:
buckets = [list(reversed(b)) for b in buckets]
a = [x for b in buckets for x in b]
print(" place %4d: %s" % (place, a))
place *= 10
return a
print()
print("stable:")
trace(data, True)
print("unstable:")
trace(data, False)
# Read the "place 1" lines: both end with the ones digits in order.
# It is the later passes where they diverge.
#
# Now the cost. Radix sort is O(d * (n + k)) -- d passes over n items with
# k buckets. It beats n log n when d is small, and d is the number of
# DIGITS, which depends on the base you choose.
import math
n = 1_000_000
print()
print("sorting %d numbers up to 2^32:" % n)
for base in (10, 256, 65536):
d = math.ceil(32 / math.log2(base))
print(" base %6d: %d passes, %6d buckets, ~%d bucket-ops" % (
base, d, base, d * (n + base)))
print(" a comparison sort: ~%d comparisons" % int(n * math.log2(n)))
# Bigger base, fewer passes, more memory for buckets. Base 256 is the
# usual answer -- four passes over a 32-bit key and a cache-friendly
# 256-entry table -- and it is comfortably under the comparison count.
Output
Guided experiments
Step through pass 1 (units). Values scatter into buckets by their last digit and are collected back in bucket order.
Check the array after pass 1. It is sorted by units only — the tens are still scrambled.
Watch pass 2. Numbers sharing a tens digit stay in their pass-1 order. That is stability doing the real work.
Note the comparison counter: zero. No two values are ever compared, which is exactly how the O(n log n) bound is sidestepped.
Count the passes. Three-digit numbers need three passes, regardless of how many values there are.
The short of it
Radix sort distributes by digit rather than comparing, achieving O(d·n) — linear when digit count is fixed. It depends entirely on stable bucketing, since each pass must preserve the ordering established by the last. Only usable on digit-decomposable keys, and it costs extra memory.
LSD and MSD
Least significant digit first is the version above: start with the rightmost digit and work left. It requires a stable inner sort and processes every digit of every element, and it is the standard choice for fixed-width numeric keys.
Most significant digit first starts from the left, partitions into buckets by the leading digit, and recurses into each bucket. It can stop early — once a bucket holds one element, that element's position is settled — which makes it better for variable-length keys such as strings.
MSD radix sort on strings is genuinely fast and is used for sorting large string collections. It is essentially a trie traversal, which is the connection worth noticing: MSD radix sort and tries organise data the same way.
LSD
MSD
Direction
Right to left
Left to right
Needs stability
Yes
No
Early termination
No
Yes
Suits
Fixed-width numbers
Variable-length strings
Recursion
None
Per bucket
Handling the awkward cases
Negative numbers. The straightforward version breaks, because digit extraction treats sign as absent. Two fixes: offset every value by the minimum so all are non-negative, or partition into negatives and non-negatives, sort each, and reverse the negative part.
Floating-point numbers. IEEE 754 floats can be radix-sorted by reinterpreting their bits as integers, with a transformation to handle the sign bit and negative ordering. Correct, fiddly, and used in high-performance libraries.
Strings of unequal length. Pad conceptually with a character that sorts before everything, or use MSD radix sort, which handles it naturally.
Very large keys. The number of passes grows with key width, so a 512-bit key means many passes. Comparison sorts become competitive.
Where it is used
GPU sorting libraries. Radix sort is the dominant GPU sorting algorithm, because its work is regular and highly parallel — no branching on comparisons.
Database sorting of integer keys at scale.
Suffix array construction, which uses radix sort internally and underlies compressed text indexes.
Histogram-based image processing, where the count array is the histogram.
Sorting fixed-width identifiers — timestamps, IDs, IP addresses.
Bioinformatics, for sorting DNA k-mers over a four-letter alphabet.
The GPU case is the most consequential today: when sorting billions of keys on a GPU, radix sort's predictable memory access and absence of branching matter far more than its theoretical complexity.
Questions people ask
How does it beat O(n log n)? That bound applies to comparison-based sorts. Radix sort never compares two elements, so the bound does not apply.
Is it always faster than quick sort? No. It wins for fixed-width integer keys at large n; comparison sorts win for arbitrary objects, small n, or very wide keys.
Does the inner sort have to be counting sort? It has to be stable. Counting sort is the natural choice because it is O(n+k) and stable.
Can it sort strings? Yes — MSD radix sort handles variable-length strings well and is effectively a trie traversal.
What base should I use? 256 for integers: four passes for 32-bit keys, and digit extraction is a shift and mask.
Is it stable? LSD radix sort is, provided the inner sort is. That is a requirement, not a bonus.
Recap in one screen
Sort by one digit at a time with a stable counting sort; after all digits, the array is sorted.
Stability is mandatory — each pass must preserve the previous passes' ordering.
O(d(n+k)), linear for fixed-width keys, which is possible because nothing is ever compared.
Base 256 is the practical choice: four passes for 32-bit integers, with shift-and-mask digit extraction.
LSD suits fixed-width numbers; MSD suits variable-length strings and is essentially a trie traversal.
Run it in Python
Sorted one digit at a time, least significant first, with the whole list printed after each pass. It looks wrong until the final digit goes through — which is the thing worth understanding here.
radix_sort.pyPython 3
# Radix sort (LSD): sort by the ones digit, then the tens, then the hundreds.
# Each pass MUST be stable, or the work of the previous pass is destroyed.
def counting_sort_by_digit(a, place):
counts = [0] * 10
for value in a:
counts[(value // place) % 10] += 1
for i in range(1, 10):
counts[i] += counts[i - 1]
out = [0] * len(a)
for value in reversed(a): # reversed => stable
digit = (value // place) % 10
counts[digit] -= 1
out[counts[digit]] = value
return out
def radix_sort(a):
a = a[:]
place = 1
while max(a) // place > 0:
a = counting_sort_by_digit(a, place)
name = {1: "ones", 10: "tens", 100: "hundreds", 1000: "thousands"}[place]
print(f"after {name:>9} digit: {a}")
place *= 10
return a
data = [170, 45, 75, 90, 802, 24, 2, 66]
print("start :", data)
print()
print("sorted:", radix_sort(data))
print()
digits = len(str(max(data)))
print(f"{len(data)} items, {digits} digits -> {digits} passes over the list.")
print("Cost is O(d * n): the number of DIGITS, not the number of items.")
Output
How the code works
(value // place) % 10Extracts one digit: divide the smaller places away, then take the remainder. Changing 10 here changes the base, and the base is the one real tuning knob radix sort has.
for value in reversed(a):Stability is not a nicety here, it is a correctness requirement. Each pass must preserve the order the previous pass established, or sorting by tens throws away the ones ordering entirely.
while max(a) // place > 0:One pass per digit of the largest value. Nothing depends on how many items there are, which is why radix sort is O(d · n).
place *= 10Least significant digit first. It reads backwards — the list looks unsorted after every pass but the last — and it is what allows a single linear pass per digit instead of recursion.
Change one thing
Print only after the ones pass. The list is sorted by last digit and otherwise scrambled — every intermediate state looks like a bug.
Make one pass unstable by iterating forwards. The final output is wrong, and it is wrong in a way that is very hard to read off the result.
Add 999999 to data. One extra item costs three extra passes over everything — d is set by the widest value, not the typical one.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.
Check yourself
0 of 3
Answer without scrolling back up.
Why must each digit pass be stable?
Sorting by tens must preserve the ones ordering among items with equal tens digits. An unstable pass silently produces a wrong final answer.
Radix sort's cost is O(d · n), where d is:
One pass per digit position, each pass linear in n. Adding a single very wide value adds passes over the entire list.
After only the ones-digit pass, the list:
Every intermediate state looks broken, which is what makes LSD radix sort hard to debug by eye. Only the final pass makes it correct.
Cheat sheet
Radix Sort
Sort by the last digit, then the next, then the next. No two values are ever compared — which is how radix sort slips past the O(n log n) barrier that binds every comparison sort.
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.