vizlearn
Home / Algorithms

Radix Sort

Algorithms & Data StructuresBy Updated

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

Time O(d·n)
Space O(n+k)
Comparisons 0

Overview

For nonnegative integers, start with the units digit and move left through the digits. Each pass groups values by the current digit, then collects the groups in order. The pass must be stable: values with the same current digit keep their previous relative order.

How least-significant-digit radix sort works

For example, after the units pass, values are ordered by units. A stable tens pass orders by tens while preserving units order among ties. Repeating through the highest digit produces the full numeric order. The visualizer lets you step through each pass and inspect how the ordering accumulates.

Try it yourself: Radix Sort

Step through the units pass, then the tens pass. Check that the array is ordered by the digits processed so far, and that equal-digit values retain their previous order.

Why stability matters

After the units pass, 21 comes before 22 because its units digit is smaller. Both have tens digit 2, so a stable tens pass keeps 21 before 22. If it reordered equal-digit values arbitrarily, it could destroy the earlier ordering.

If a pass reorders equal-digit values arbitrarily, it can undo the ordering established by less significant digits. Stability lets each new pass refine the previous result.

Cost and limits

With n keys, d digit positions, and digit base k, counting-based passes take O(d(n + k)) time and typically O(n + k) extra space. For fixed-width keys and a fixed base, d is bounded, so runtime grows linearly with the number of keys.

That does not contradict the Ω(n log n) lower bound for comparison sorting: radix sort uses the representation of the keys instead of learning their order only through comparisons. It is useful for large batches of fixed-format integers, strings, or identifiers when the number of passes and extra memory are reasonable. It is a poor fit for arbitrary objects or keys with costly, unbounded representations.

Choose a base

For a 32-bit nonnegative integer, base 256 processes one byte per pass, so it needs four digit passes and a 256-entry count array. A larger base reduces the number of passes but uses a larger count array. Practical performance also depends on memory traffic, implementation, and hardware; the asymptotic bound alone does not guarantee it will beat a comparison sort.

Sources and next steps

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
Output
How the code works
  1. (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.
  2. 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.
  3. 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).
  4. 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.




Predict, then reveal
About to run: set values to its maximum (12). Before it does — what happens to the readout?
Committing to an answer first is the point — the reveal runs the experiment on the visualisation above and reads the real value back, so nothing here is scripted.
Check yourself
0 of 3
Answer without scrolling back up.
  1. Why must each digit pass be stable?
  2. Radix sort's cost is O(d · n), where d is:
  3. After only the ones-digit pass, the list:





 Cheat sheet
Radix Sort
Sort integers digit by digit with zero comparisons and beat the O(n log n) lower bound that comparison-based sorts cannot escape.
ALGORITHMS · vizlearn.in/dsa/radix_sort.html
More in Algorithms
AlgorithmsStacks (LIFO)AlgorithmsQueues (FIFO)AlgorithmsLinked ListsAlgorithmsHash Tables and Hashing
About the author
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.
About VizLearnGitHubLinkedInContact