How radix sort works
Radix sort sorts numbers the way a post office sorts letters by PIN code: one digit at a time. The surprise is the order. LSD (least significant digit) radix sort starts with the last digit, the ones, then the tens, then the hundreds. Each pass puts the values into 10 groups, 0 to 9, by that digit alone.
Why does starting from the wrong end work? Because every pass is stable: values with the same digit keep the order the previous pass gave them. After the ones pass the array is sorted by its last digit. The tens pass groups by the tens digit, and inside each group the ones order survives, so the array is now sorted by its last two digits. After the hundreds pass it is sorted by all three. In the visualizer's array, 170 and 75 both have tens digit 7; the ones pass already put 170 (ones digit 0) ahead of 75 (ones digit 5), and the tens pass keeps them that way.
Each digit pass is a counting sort with 10 counters: count how many values have each digit, take running totals, then walk the array from the right and place every value. Short numbers count as having leading zeros, which is why 2 and 45 land in the 0 group of the hundreds pass.
The number of passes is the number of digits d of the largest value, so the cost is O(d · (n + 10)). For numbers with a fixed number of digits that is linear in n. Digits do not have to be decimal: real implementations usually take 8 bits at a time, so any 32-bit integer needs exactly 4 passes with 256 counters each.
The algorithm in 5 steps
- 1 Find the largest value; its number of digits is the number of passes.
- 2 Start with
exp = 1, the ones digit. The digit ofvisv // exp % 10. - 3 Run a stable counting sort on that digit: count, take running totals, place values from right to left into
out, copy back. - 4 Multiply
expby 10 and repeat for the tens, hundreds... untilexpis bigger than the largest value. - 5 Negative values: shift everything up by −min before sorting and back down after, as the code here does.
Worked example
These are the seven 3-digit numbers from Figure 8.3 of CLRS (Introduction to Algorithms), run through the same code as the visualizer. Each row is the array after one digit pass: ones, then tens, then hundreds. The counting and placing steps inside each pass are counted in the total but not listed.
Input: [329, 457, 657, 839, 436, 720, 355]
- Step 40 After the ones pass: 720, 355, 436, 457, 657, 329, 839. The values are now in order of their last digit, and values with the same digit kept their input order. 720355436457657329839
- Step 79 After the tens pass: 720, 329, 436, 839, 355, 457, 657. The values are now in order of their last 2 digits, and values with the same digit kept their order from the pass before. 720329436839355457657
- Step 118 After the hundreds pass: 329, 355, 436, 457, 657, 720, 839. That was the last digit, so the array is sorted. 329355436457657720839
Total for this run: 3 digit passes, 69 counter updates and 42 writes, in 119 animation steps. Result: 329, 355, 436, 457, 657, 720, 839.
Time and space complexity
Best
O(d · (n + k))Every pass runs in full whatever the input order. d is the number of digits of the largest value and k the number of possible digits, 10 here.
Average
O(d · (n + k))The same d passes. With d and k fixed, for example 32-bit integers in 4 byte passes of 256 counters, that is O(n).
Worst
O(d · (n + k))One huge value makes d large for everyone: [1, 2, 3, 1000000000] needs 10 decimal passes to sort four numbers.
Space
O(n + k)An output array of n values and k counters, reused on every pass. Not in place.
- Stable:
- Yes
- In place:
- No
- Comparison sort:
- No
- Works on:
- Integers and fixed-length keys
Same 8 numbers, comparison sorts vs radix sort
Every comparison sort needs at least ⌈log₂(n!)⌉ comparisons in the worst case, 16 for 8 values, and that grows like n log n. Radix sort never compares two values to order them: on the visualizer's numbers it runs 3 digit passes, with 75 counter updates and 48 writes. Computed from the code on these pages, not typed in.
| Algorithm | Comparisons | Other work |
|---|---|---|
| Radix sort | 0 (after finding the largest value) | 75 counter updates, 48 writes |
| Merge sort | 17 | 24 writes |
| Quick sort | 39 | 8 swaps |
| Heap sort | 26 | 18 swaps |
| Insertion sort | 21 | 16 shifts |
Fewer operations on 8 numbers is not the point; the growth is. Comparison sorts grow like n log n. Radix sort grows like d · (n + 10), where d is the number of digits in the largest value.
When to use it, and when not to
Good fit
- Large numbers of integers with a bounded size: IDs, timestamps, 32- or 64-bit keys. With byte-sized digits a 32-bit key needs 4 passes, whatever n is, so for millions of keys it can beat O(n log n) sorts.
- Fixed-length keys made of characters or digits: dates as YYYYMMDD, PIN codes, phone numbers, equal-length strings. LSD radix sort on each character position sorts them in d passes.
- You need a stable sort by a composite key: sort by the minor key first, then by the major key with a stable sort. That is the LSD idea, and it is how punched-card sorting machines were operated, one column per run.
- As a building block: suffix-array construction and other string algorithms use radix sort on integer ranks to get linear-time passes.
Pick something else when
- Few values or values of very different lengths. One huge number forces extra passes for everyone, and for small n a comparison sort is simpler and as fast.
- Keys that are not integers or fixed-length strings, such as floats compared with a tolerance or objects sorted by a custom rule. (IEEE floats can be radix sorted after a bit trick, but that is beyond a first implementation.)
- Memory is tight: radix sort needs an n-sized output array. Heap sort works in place.
- You just need to sort in application code. Your language's built-in sort is tuned, tested and usually fast enough; reach for radix sort when profiling says sorting integer keys is the bottleneck.
Common mistakes and bugs
-
1.Using an unstable sort for each digit
LSD radix sort is only correct if each pass is stable. Take
[25, 21]: the ones pass gives[21, 25]. In the tens pass both have digit 2, and an unstable pass is free to output[25, 21], which is wrong. Counting sort placed right to left, as here, is stable. -
2.Starting from the most significant digit with the same loop
Running the passes hundreds, then tens, then ones lets the last pass (the ones) undo the earlier ones:
[21, 15]sorted by tens gives[15, 21], then by ones gives[21, 15]. MSD radix sort exists, but it must recurse into each digit group separately instead of re-sorting the whole array. -
3.Feeding it negative numbers as they are
In Java,
-5 % 10is −5, socount[-5]throws an exception. In Python,-5 // 1 % 10is 5, so −5 is quietly sorted as if it were 5. Shift all values up by −min first and back after, as the code here does, or sort negatives and positives separately. -
4.Letting exp overflow in Java
With
int exp, the pass after 10⁹ computes 10¹⁰, which overflows to 1,410,065,408. For a largest value above that, the loop runs an extra pass on a meaningless "digit" and can scramble a sorted array. The Java code here declaresexpaslong. -
5.Recomputing the digit with floating point
Writing the digit as
Math.floor(v / Math.pow(10, p)) % 10or withlog10to count digits invites rounding errors on large values. Keepexpas an exact integer that is multiplied by 10 each pass, and get the number of passes from the loop condition, not from a logarithm.
Interview questions
Try answering before you open the model answer.
Q1 Why does LSD radix sort work when it starts from the least significant digit?
Model answer: Each pass is stable. By induction, after pass p the array is sorted by its last p digits: the new pass orders by digit p, and values with an equal digit p keep the order of the previous pass, which was by the last p − 1 digits. After the last digit the array is sorted by the whole number.
Q2 What is the time complexity of radix sort, and when is it better than O(n log n)?
Model answer: O(d · (n + k)) for n values with d digits of k possible values each (CLRS, Lemma 8.3). It is better when d is small and fixed: 32-bit integers take 4 passes with k = 256, which is linear in n. If d grows with n, for example distinct values need about log n digits, the advantage over a good comparison sort shrinks.
Q3 Sort n integers in the range 0 to n² − 1 in O(n) time.
Model answer: Write each number in base n: it has at most two digits, v // n and v % n. Two passes of radix sort, each a counting sort with k = n counters, take O(n) each. Counting sort alone would need n² counters, and comparison sorts need O(n log n).
Q4 What is the difference between LSD and MSD radix sort?
Model answer: LSD processes digits from the right, always re-sorting the whole array with a stable pass, which is simple and iterative but requires keys of equal length (or padding). MSD starts from the left, splits the values into groups by that digit and recurses into each group, so it can stop early, handles variable-length strings naturally and resembles a trie traversal.
Q5 Why is counting sort used inside radix sort and not, say, quick sort?
Model answer: Two reasons. The digit has only 10 (or 256) possible values, which is exactly where counting sort is O(n + k), linear per pass. And it is stable, which LSD radix sort needs for correctness. Quick sort is neither linear nor stable, so the passes would cost O(n log n) each and could give a wrong result.
Frequently asked questions
What is the time complexity of radix sort?
O(d · (n + k)): n values, d digits in the largest value, k possible digit values (10 for decimal). Every pass runs in full, so best and worst case are the same. With fixed-size keys, such as 32-bit integers sorted a byte at a time, that is linear time.
Is radix sort stable?
Yes, LSD radix sort is stable, and it has to be built from a stable digit sort to work at all. Each pass here is a counting sort that places values from right to left, so values with the same digit keep their order. That is also why equal values in the whole array keep their original order.
Is radix sort faster than quick sort?
Sometimes. For millions of integer keys of fixed size, radix sort does a few linear passes and no comparisons, and can win. For small arrays, mixed key lengths or general objects, a tuned comparison sort such as quick sort or Timsort is usually faster and needs no extra memory, which is why built-in sorts are comparison sorts.
Can radix sort handle negative numbers?
Not directly, because the digits of a negative number are not defined the same way, and the % operator behaves differently in Python and Java. The usual fix, used in the code on this page, is to subtract the minimum from every value, sort, then add it back. The visualizer itself draws digits of values 0 to 999.
Why does radix sort start from the least significant digit?
Because each later pass is stable, it keeps the order of the earlier passes for values with the same digit. Sorting by the ones, then tens, then hundreds leaves the hundreds digit, the most important one, decided last, with ties already ordered by the lower digits. Starting from the most significant digit needs recursion into groups instead.