Radix sort
Sort numbers digit by digit, starting from the last digit, using a stable bucket pass for each digit.
O(d × n)Space O(n)3 practice problemsStep-through pictureThe idea
Radix sort sorts whole numbers without comparing them. It looks at one digit at a time. First it puts the numbers into ten buckets by their ones digit, keeping their order inside each bucket, and joins the buckets back together. Then it does the same for the tens digit, then the hundreds digit, and so on.
It sounds backwards to start with the last digit, but it works because each pass is stable: numbers with the same digit keep the order the earlier passes gave them. After the final pass, numbers are ordered by their highest digit, and ties are already ordered by the lower digits.
For n numbers with d digits, radix sort takes O(d × n) time. For fixed-size keys, like 32-bit numbers or 6-character codes, d is a small constant, so it is linear.
An everyday example
Sorting mail by postal code, last digit first
A mail room sorts letters by 3-digit postal code using ten trays labeled 0 to 9. First the clerk drops each letter into the tray of its last digit, then stacks the trays in order, 0 on top. Then she sorts that stack into the trays by the middle digit, never reordering letters inside a tray, and stacks again. One more round with the first digit, and the whole stack is in postal-code order.
| In the example | In the code |
|---|---|
| The ten trays | buckets, one per digit 0 to 9 |
| The digit being looked at | Math.floor(value / place) % 10 |
| Dropping a letter on top of its tray | buckets[digit].push(value) |
| Stacking the trays in order | result = buckets.flat() |
| Moving to the next digit | place *= 10 |
From the slow way to radix sort
- Counting sort is fast when the range of values is small. For values up to a billion it would need a billion slots. But every value up to a billion has at most 10 decimal digits, and each digit has only 10 possible values. Can we sort one digit at a time, with ten slots each time?
- The natural first idea is to start with the most important digit: put numbers into ten buckets by their first digit, then sort inside each bucket by the next digit. That works, but it needs a separate recursive sort inside every bucket, which gets complicated.
- The surprising fix is to start from the last digit instead. Sort everything by the ones digit. Then sort everything by the tens digit, but in a stable way, so numbers with the same tens digit keep the order the first pass gave them. Those numbers are then ordered by their last two digits.
- Each later pass adds one more digit of order. Pushing each number to the end of its bucket and joining the buckets from
0to9is stable by itself, so each pass is one simple loop. Repeat forplace = 1,10,100, and so on, whileplace <= largest. That loop is least-significant-digit radix sort.
How it works
- Find
largest, the biggest number, to know how many digits to process. - Start with
place = 1(the ones digit). - Make ten empty buckets. For each value in the current order, compute
digit = Math.floor(value / place) % 10and push the value intobuckets[digit]. - Join the buckets in order, 0 to 9, into the new
result. - Multiply
placeby 10 and repeat whileplace <= largest.
Watch it run
This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.
See every step at onceThe same run, laid out side by side
The code
Point at a note to light up the lines it explains.
function radixSort(items) {if (items.length === 0) return items;const largest = Math.max(...items);let result = [...items];for (let place = 1; place <= largest; place *= 10) {const buckets = Array.from({ length: 10 }, () => []);for (const value of result) {const digit = Math.floor(value / place) % 10;buckets[digit].push(value);}result = buckets.flat();}return result;}
How fast it is
| Time | O(d × n) |
|---|---|
| Extra memory | O(n) |
d is the number of digits in the largest value. Each pass moves all n numbers into buckets and back. The buckets hold all n numbers during a pass.
- Best case
O(d × n)Every input with
ddigits in its largest value takesdfull passes, even a sorted list like[10, 20, 30]. - Average case
O(d × n)The order of the input doesn't change the work: each pass places all
nnumbers once and joins 10 buckets. - Worst case
O(d × n)One huge value makes
dlarge for everyone:[3, 1, 9, 4000000000]needs 10 passes, even though most numbers have one digit.
Common mistakes
- Starting from the highest digit with this simple loop. Later passes then scramble the earlier order. Most-significant-first radix sort needs recursion inside each bucket.
- Using a pass that is not stable, such as sorting each bucket by full value or inserting at the front. Earlier digits' work is lost.
- Writing
new Array(10).fill([]), which puts the same array in all ten slots, so every number lands in one shared bucket. - Running it on negative numbers or decimals.
Math.floor(-7 / 1) % 10is-7, which is not a bucket index.
When to use it
Look for these clues in a problem:
- The keys are non-negative whole numbers or fixed-length strings, such as IDs, dates like
20240315, or hex colors. - There are many keys and you want to beat
O(n log n). - The question asks about the order after each digit pass.
Check yourself
Answer each one in your head first, then open it.
Why must each pass be stable?
Ties on the current digit are broken only by the order left by earlier passes. An unstable pass would scramble that order and lose the work of the lower digits.
How many passes does this code make for [45, 9, 1200]?
Four, for place = 1, 10, 100, and 1000, because largest is 1200. The loop stops when place becomes 10000.
What goes wrong with new Array(10).fill([]) for the buckets?
fill puts the same array object in all ten slots, so every number is pushed into one shared bucket. Array.from with a function creates ten separate arrays.
Why doesn't starting from the most significant digit work with this simple loop?
A later pass on a lower digit would reorder numbers across the whole list, undoing the order by the more important digit. Most-significant-first needs a separate sort inside each bucket.
Practice problems
Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.
0 of 3 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.
Start practicingGo further
You don't need these to start practicing. Open one when you want more.
Why it works
The reasoning that makes it always right
The rule after the pass for place is: result is sorted by the number formed by the last digits up to place. After the ones pass, it is sorted by the ones digit. That is true because joining buckets 0 to 9 in order sorts by the digit used for the buckets.
Each pass keeps the rule for one more digit. Take two numbers after the tens pass. If their tens digits differ, the bucket order puts the smaller tens digit first, which is right. If their tens digits are equal, they sit in the same bucket in the order the ones pass left them, because each value is pushed to the end of its bucket in the current order. So ties on the tens digit are broken by the ones digit, which is exactly ordering by the last two digits.
The loop ends when place is bigger than largest. At that point every number has run out of digits, since a number smaller than place has only zeros from that digit up. So sorting by all the digits processed is the same as sorting by the whole value, and result is sorted.
Going deeper
3 more ideas
Why starting from the last digit works
After the pass for a digit, the numbers are sorted by that digit, and numbers with the same digit are still in the order of the previous passes, because pushing to the end of a bucket keeps order (the pass is stable). So after the tens pass, the list is sorted by the last two digits. By induction, after the last pass it is sorted by all the digits, which is the full number.
How long it takes
Each pass looks at every number once and joins 10 buckets: O(n + 10). There is one pass per digit of the largest number, d passes, so the total is O(d × (n + 10)), written O(d × n). Using base 256 (one byte per pass) instead of base 10 makes d smaller for big numbers.
Strings and negative numbers
Fixed-length strings sort the same way, using character codes as digits, last character first. Negative numbers need care: sort the negatives and positives separately (or add an offset to make all values non-negative), because a minus sign is not a digit.
Work it by hand
Every step in a table, with why
Sort 7 numbers with up to 3 digits. The first pass is shown number by number; later passes show only their buckets.
items = [507, 31, 264, 8, 93, 260, 35]
| Step | place | value | digit | buckets used | result | What happens | Why |
|---|---|---|---|---|---|---|---|
| 1 | 1 | 507 | 7 | 7: 507 | - | Ones digit 7 | largest is 507, so the passes are for place = 1, 10, and 100. |
| 2 | 1 | 31 | 1 | 1: 31 | - | Ones digit 1 | Math.floor(31 / 1) % 10 is 1. |
| 3 | 1 | 264 | 4 | 4: 264 | - | Ones digit 4 | Each value goes to the end of its bucket. |
| 4 | 1 | 8 | 8 | 8: 8 | - | Ones digit 8 | A one-digit number is handled the same way. |
| 5 | 1 | 93 | 3 | 3: 93 | - | Ones digit 3 | No comparisons between numbers, only digit lookups. |
| 6 | 1 | 260 | 0 | 0: 260 | - | Ones digit 0 | 260 goes to bucket 0, so it will come first after this pass. |
| 7 | 1 | 35 | 5 | 5: 35 | [260, 31, 93, 264, 35, 507, 8] | buckets.flat() | Joining buckets 0 to 9 gives the list sorted by the last digit. |
| 8 | 10 | all | tens | 0: 507, 8; 3: 31, 35; 6: 260, 264; 9: 93 | [507, 8, 31, 35, 260, 264, 93] | Sorted by the last two digits | 507 and 8 both have tens digit 0. 507 stays first because it came first in the last pass. |
| 9 | 100 | all | hundreds | 0: 8, 31, 35, 93; 2: 260, 264; 5: 507 | [8, 31, 35, 93, 260, 264, 507] | Sorted by all three digits | Inside bucket 0, the order 8, 31, 35, 93 comes from the earlier passes. 260 stays before 264 for the same reason. |
| 10 | 1000 | - | - | - | [8, 31, 35, 93, 260, 264, 507] | 1000 <= 507 is false: stop | No number has a thousands digit, so the loop ends. |
It returns [8, 31, 35, 93, 260, 264, 507] after 3 passes of 7 numbers each: 21 bucket placements and no comparisons between numbers.
Compared with other ways
When to pick something else
| Approach | Time | Extra memory | Choose it when |
|---|---|---|---|
| Radix sort | O(d × n) | O(n) | Many whole numbers or fixed-length codes with few digits, where d is small and the input is large. |
| Counting sort | O(n + k) | O(n + k) | The range k of values is small. It is a single pass and simpler. |
Comparison sort (built-in sort) | O(n log n) | O(n) | General data, decimals, negative numbers mixed in, or when d would be close to log₂ n anyway. |
Extra memory: O(n): the ten buckets hold all n numbers during a pass, and result is a new array of n numbers. The input array is not changed.
How the steps grow
- Radix sort
O(d × n) - Counting sort
O(n + k) - Comparison sort (built-in
sort)O(n log n)
| Approach | n = 10 | n = 1,000 | n = 1,000,000 |
|---|---|---|---|
| Radix sort | 100 | 1 million | 1 trillion |
| Counting sort | 20 | 2,000 | 2 million |
Comparison sort (built-in sort) | 33 | 9,966 | 20 million |
Inputs that need care
5 tricky inputs
- An empty list
[] - The first line returns it at once. Without that check,
Math.max()of nothing is-Infinity, and the loop would not run anyway. - All zeros:
[0, 0] largestis0, so1 <= 0is false and the copy is returned as it is, which is already sorted.- Negative numbers:
[12, -7, 5] Math.floor(-7 / 1) % 10is-7, andbuckets[-7].pushthrows a TypeError. Sort negatives and non-negatives separately, or add an offset to make every value non-negative.- Only negative numbers:
[-3, -9] largestis-3, so the loop never runs and the copy comes back unsorted, with no error. That silent wrong answer is worse than a crash.- Decimals:
[2.7, 2.5, 1] - Digits are taken after
Math.floor, so the fractional part is ignored and the result is[1, 2.7, 2.5]. Scale decimals to whole numbers first, such as cents instead of dollars.
Variations and follow-ups
Twists interviewers add
Bigger base
Use 256 buckets and take one byte per pass with (value >> shift) & 255. A 32-bit number then needs only 4 passes instead of up to 10. Larger bases mean fewer passes but more buckets to join each time.
Counting sort for each pass
Instead of arrays of buckets, count how many numbers have each digit, turn the counts into starting positions, and copy into one output array. It avoids creating many small arrays and is how fast implementations work.
Most-significant-digit first
Bucket by the first digit, then recurse into each bucket with the next digit. It can stop early on buckets of size 1, and it sorts strings of different lengths in dictionary order.
Fixed-length strings
Codes like "AB12" sort the same way: use character codes as digits, from the last character to the first. Each pass needs as many buckets as there are possible characters.
In an interview
Spot it, explain it, answer follow-ups
- Spot it when the input is "non-negative integers" with a large range and the question demands linear time, or when sorting fixed-length strings like IDs or dates written as
YYYYMMDD. - Explain the surprising order first: "I sort by the last digit first, and each pass is stable, so earlier passes break the ties of later ones". That sentence is the whole proof.
- Test by hand with numbers of different lengths, like
[5, 120, 31], and with two numbers that share a digit, to show that a stable pass keeps the earlier order. - The usual follow-up is "isn't
O(d × n)justO(n log n)in disguise?". Answer: for numbers up toM,dis aboutlog₁₀ M, which depends on the range, not onn. For 32-bit numbers,dis a fixed 10 (or 4 with base 256) however largengets.
Where frontend code uses it
The same idea in real UI code
- Sorting fixed-format keys, such as dates stored as
YYYYMMDDnumbers or 6-digit hex colors, digit by digit. - Data-heavy tools that sort large typed arrays of numbers (for example, ordering points for a scatter plot) sometimes use radix sort, since it is linear for fixed-width keys.
- Sorting by several fields with stable passes, least important field first, is the same idea used by table UIs that remember earlier sorts.