Digits read
Moves
Pass

  • Bucket in use
  • Just moved
  • Copied back
  • In place

More about radix sort

Radix sort

Radix sort sorts whole numbers without ever comparing two of them. It sorts the list by the ones digit, then by the tens digit, then by the hundreds, each time moving the values into ten buckets and copying them back in order. Watch the buckets fill in the row under the list, one move at a time, and see the list become sorted by more and more digits. Press Play to watch the sort, or Step and Back to go one move at a time. Drag the step slider to jump anywhere. The buckets 0 to 9 sit side by side in the row under the list. The tiles count digits read, moves and passes. Choose how many bars, how they start, or type your own numbers up to 999. With the board selected, the arrow keys step, the space bar plays and pauses, and Home and End jump to the start and the end.

How it works

  1. Choose how many bars and how they start, or type your own whole numbers up to 999 to see the hundreds pass.
  2. Press Play, or use Step and Back to move one value at a time. Drag the step slider to jump anywhere in the sort.
  3. Watch each pass: count the digits, move every value into its bucket, then copy the buckets back.

How radix sort works

Look only at the last digit of every number and sort the list by it: put each number into one of ten buckets, 0 to 9, keeping the order in which they came, then copy the buckets back one after another. Do the same with the tens digit, then the hundreds. Because each pass keeps the order of numbers that share a digit, the earlier passes still decide the order among them, and after the last pass the whole list is sorted.

No comparisons at all

Comparison sorts need at least about n log₂ n comparisons in the worst case, whatever clever trick they use. Radix sort sidesteps that limit by reading digits instead: each pass reads one digit of every value and moves every value twice, so d digits take d passes and the work grows with n · d. For long lists of short keys that pays off: a million numbers up to 999 take three passes, where a comparison sort needs around 20 million comparisons. The price is that it only works for keys made of digits or characters, and it needs room for the buckets.

Frequently asked questions

How does radix sort work?

It sorts the numbers by their last digit, then by the digit before it, and so on up to the first digit. Each pass puts the numbers into ten buckets by that digit, keeping their order, and copies the buckets back. After the pass for the most significant digit the list is sorted.

Why start with the last digit?

Because each pass is stable: numbers with the same digit keep the order the earlier passes gave them. So the last pass, on the first digit, decides the order, and ties are broken by the digits already sorted. This is called LSD (least significant digit) radix sort.

Is radix sort faster than quicksort?

It can be, for many short keys: its work grows with the number of values times the number of digits, with no n log n. For few values, very long keys, or data that is not made of digits, quicksort and merge sort are usually faster and simpler.

How does it relate to counting sort?

Each pass of radix sort is a counting sort on one digit: count how many values have each digit, work out where each bucket starts, and move the values there in order.

Are my numbers sent anywhere?

No. The sort runs in your browser, and your last settings stay in this browser's local storage.

Ready to try it?

Open PictorX in your browser — no install, no credit card required to start.

Go to Editor