Skip to content

level 3 · Sorting

Radix Sort

Sort by the last digit first. It sounds backwards, and it's the only way it works.

10 min 85 XP

what is it

Start here

Radix sort takes counting sort's trick — no comparisons — and fixes its fatal flaw. Counting sort dies when the range of values is large. Radix sort simply never looks at whole values. It sorts by one digit at a time.

And it starts with the **last** digit. That feels completely wrong: surely the first digit matters most? Sit with that discomfort, because it's the whole lesson.

The reason it works is **stability**. Each pass must keep equal digits in the order they were already in. So when you sort by the tens digit, two numbers that tie there stay in the order that the units pass left them — meaning the units pass's work is *preserved*, not destroyed. Each pass adds a more significant digit while quietly keeping everything the earlier passes achieved.

Go most-significant-first instead and each pass scrambles the last one's work. You'd have to sort each group separately and recursively, and the elegance evaporates.

The payoff: O(d × n) for d digits. On a big pile of fixed-width keys — IDs, dates, fixed-length numbers — that genuinely beats n log n. It's how card-sorting machines physically worked, decades before anyone wrote it down as an algorithm.

real-life analogy

Picture it

Sorting punched cards with a physical machine

A card sorter drops each card into one of ten bins based on a single digit column, then you stack the bins back up in order — bin 0 on the bottom, bin 9 on top. Do the units column, restack, do the tens column, restack. Because the machine never reorders cards within a bin, each pass keeps the last one's work. After the last column, the deck is sorted.

interactive visualization

Watch it run

Fix the input above and the animation will come back.

complexity

What it costs

best case
O(d × n)
average
O(d × n)
worst case
O(d × n)
extra memory
O(n + b)

d passes over n items, where d is the number of digits and b the base (10 here). On fixed-width keys d is a small constant, so this is effectively linear — genuinely faster than n log n. On values with wildly different lengths, d starts to hurt.

  • O(1)
  • O(log n)
  • O(n) · this one
  • O(n log n)
  • O(n²)
input size →work →

common mistakes

Common traps

  • Sorting from the most significant digit first.

    Each pass would destroy the last one's work. Least-significant-first, combined with stability, is what makes the passes accumulate instead of fight.

  • Using an unstable sort for each digit pass.

    Stability is not a nice-to-have here — it's the load-bearing wall. Break it and the algorithm is simply wrong.

  • Forgetting negative numbers.

    Digits don't have signs. Split into negatives and positives, sort separately, and reverse the negatives — or the minus signs will be silently ignored.

quiz

Check yourself

Three questions. Get them all right to finish the lesson.

+85 XP

01Why does radix sort start with the LAST digit?

02What breaks radix sort completely?

03What's radix sort's complexity, and when does it beat n log n?

practice

Solve it on LeetCode

You've seen it run — now write it yourself. These are real LeetCode problems that use exactly this idea, from gentlest to toughest.