Radix Sort: Sorting Integers Without Comparing Them
Radix sort orders integers digit by digit with a stable counting sort, beating O(n log n) for bounded-width numbers. Walkthrough, JavaScript, and complexity.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Every sort you learned first — quicksort, mergesort, heapsort — works by asking one question over and over: is a bigger than b? That comparison is the bottleneck, and it caps every comparison sort at O(n log n). Radix sort refuses to play that game. It never compares two numbers directly. Instead it sorts by one digit at a time and lets the digits do the ordering for free.
The payoff is real: for integers with a bounded number of digits, radix sort runs in linear time. The catch is that it leans entirely on a subtle property of its inner sort — stability — and getting that wrong silently breaks everything.
The problem
Given an array of non-negative integers, return them in ascending order. Nothing exotic — the same output a comparison sort would give — but we want to hit it without a single a > b comparison.
Input: [90, 45, 8, 75]
Output: [8, 45, 75, 90]The numbers have different widths (one digit up to two digits), which is exactly the case radix sort has to handle cleanly. The largest value, 90, has two digits — that number, two, decides how many passes we make.
The brute force baseline
The default move is a comparison sort. Here's insertion sort, which any interviewer recognizes as the honest baseline:
function insertionSort(arr) {
for (let i = 1; i < arr.length; i++) {
const key = arr[i];
let j = i - 1;
while (j >= 0 && arr[j] > key) { // the comparison we want to avoid
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
return arr;
}This is O(n²) in the worst case, and even the best comparison sorts (quicksort, mergesort) bottom out at O(n log n). That log n factor is not an accident of a clumsy algorithm — it is a proven lower bound. Any sort that only learns about the data through pairwise comparisons must make at least log₂(n!) ≈ n log n comparisons to distinguish all possible orderings. If we want to go faster, we have to stop comparing.
The key insight: sort by digit, least significant first
Here is the reframe. A number like 802 is really three independent keys stacked together: a hundreds digit, a tens digit, and a ones digit. If we could sort the array by each of those keys and have the results compose, we'd never compare full numbers at all.
Radix sort processes digits from the least significant (ones) to the most significant (LSD radix sort). The magic that makes this work is stability: a stable sort preserves the relative order of elements that tie on the current key.
Walk the logic. After sorting by the ones digit, all numbers are correctly ordered by their last digit. Now sort by the tens digit with a stable sort. Two numbers with the same tens digit keep the order they already had — which was the ones-digit order. So they end up ordered by tens-then-ones, i.e. fully correct up to two digits. Each pass extends the sorted prefix by one more digit, and after d passes the whole number is sorted.
The inner sort has to be stable and fast. Counting sort is both. Because a single digit is always 0–9, counting sort only needs 10 buckets — its cost per pass is O(n + 10), and it preserves ties. That is the engine radix sort runs on. (For a deeper look at the engine itself, see the counting-sort posts linked at the end.)
The optimal solution
This is the exact algorithm the visualizer steps through. radixSort finds the max to know how many passes to run, then calls a stable counting sort once per digit position, with e (the exponent) marching from 1 to 10 to 100.
function countingSortStable(arr, e) {
let count = new Array(10).fill(0);
// 1. Tally how many numbers have each digit at position e.
for (let x of arr) {
let digit = Math.floor(x / e) % 10;
count[digit]++;
}
// 2. Prefix sums: count[d] becomes the end position for digit d.
for (let i = 1; i < count.length; i++) {
count[i] = count[i] + count[i - 1];
}
// 3. Place right-to-left so equal digits keep their relative order.
let sortedArr = new Array(arr.length);
for (let i = arr.length - 1; i >= 0; i--) {
let curr = Math.floor(arr[i] / e) % 10;
let x = count[curr];
sortedArr[x - 1] = arr[i];
count[curr]--;
}
// 4. Copy back so the next pass sees the new order.
for (let i = 0; i < arr.length; i++) {
arr[i] = sortedArr[i];
}
}
function radixSort(arr) {
let max = Math.max(...arr);
for (let e = 1; Math.floor(max / e) > 0; e = e * 10) {
countingSortStable(arr, e);
}
return arr;
}Two lines carry the whole idea. Math.floor(x / e) % 10 extracts the digit at position e — divide to drop the lower digits, mod 10 to keep only the one you want. And the placement loop runs right to left (i = arr.length - 1 down to 0): combined with decrementing count[curr] after each placement, this is precisely what keeps the sort stable.
Walkthrough
Trace [90, 45, 8, 75]. Max is 90, so we make two passes: ones, then tens. Watch 45 and 75 — they tie on the ones digit (both end in 5), and stability is what keeps 45 ahead of 75 all the way to the end.
Pass 1 — ones digit (e = 1). Digits are 90→0, 45→5, 8→8, 75→5.
| Bucket (digit) | 0 | 1–4 | 5 | 6–7 | 8 | 9 |
|---|---|---|---|---|---|---|
| Frequency | 1 | 0 | 2 | 0 | 1 | 0 |
| Prefix sum (end position) | 1 | 1 | 3 | 3 | 4 | 4 |
Placing right-to-left into sortedArr:
| Read arr[i] | Digit | count[digit] | Lands at index | sortedArr so far |
|---|---|---|---|---|
| 75 (i=3) | 5 | 3 | 2 | [_, _, 75, _] |
| 8 (i=2) | 8 | 4 | 3 | [_, _, 75, 8] |
| 45 (i=1) | 5 | 2 | 1 | [_, 45, 75, 8] |
| 90 (i=0) | 0 | 1 | 0 | [90, 45, 75, 8] |
Array after pass 1: [90, 45, 75, 8]. Note 45 landed before 75 — the right-to-left scan met 75 first and put it in the last of the two slots reserved for digit 5.
Pass 2 — tens digit (e = 10). Digits are 90→9, 45→4, 75→7, 8→0.
| Read arr[i] | Digit | Lands at index | sortedArr so far |
|---|---|---|---|
| 8 (i=3) | 0 | 0 | [8, _, _, _] |
| 75 (i=2) | 7 | 2 | [8, _, 75, _] |
| 45 (i=1) | 4 | 1 | [8, 45, 75, _] |
| 90 (i=0) | 9 | 3 | [8, 45, 75, 90] |
Array after pass 2: [8, 45, 75, 90] — fully sorted. Because 45 and 75 had different tens digits, this pass separated them correctly, and everything else fell into place. Two passes, no comparison of full numbers.
Complexity
Let n be the array length, d the number of digits in the largest value, and k the base (10 here).
| Metric | Value | Why |
|---|---|---|
| Time | O(d · (n + k)) | d passes; each counting sort does one O(n) tally, one O(k) prefix scan, one O(n) placement |
| Space | O(n + k) | the sortedArr output buffer (n) plus the count buckets (k) |
| Stable? | Yes | right-to-left placement preserves ties, which is what makes the passes compose |
When d and k are small constants — say sorting 32-bit integers, where d is fixed — the whole thing collapses to O(n), genuinely linear and faster than any comparison sort for large n. The trade-off is the extra O(n) buffer: radix sort is not in-place.
Common mistakes
- Using an unstable inner sort. Swap counting sort for quicksort inside each pass and radix sort breaks. Ties on the current digit get reordered arbitrarily, wiping out the ordering the previous passes built. Stability is not optional.
- Placing left-to-right. Scanning
i = 0 → n-1while decrementingcount[curr]produces an unstable result. The right-to-left direction paired with the ending-position prefix sums is the specific combination that stays stable. - Sorting by most significant digit first (naively). LSD is the easy, composable version. Starting from the most significant digit needs recursion and per-bucket partitioning — a different, trickier algorithm.
- Feeding it negative numbers.
Math.floor(x / e) % 10assumes non-negative input. Negatives need special handling — offset every value by the minimum, or sort magnitudes and split by sign. - Assuming it's always faster. For small
n, or when the max value has many digits (larged), the constant factors and the O(n) buffer can make a good comparison sort win. Radix shines on largenwith bounded digit width.
Where this pattern shows up next
Radix sort sits at the intersection of counting sort and the broader family of non-comparison sorts. These build directly on the ideas here:
- Counting Sort — the O(n + k) bucket-tally sort that radix runs once per digit.
- Counting Sort - Stable - Logic — why the prefix-sum-and-place-backwards trick keeps ties in order.
- Counting Sort - Stable - Code — the exact stable implementation radix sort embeds.
- Quick Sort — the comparison-based O(n log n) sort radix sidesteps entirely.
You can also step through Radix Sort interactively to watch the digit buckets fill and the array reorder one pass at a time.
FAQ
Why does radix sort need a stable inner sort?
Because each pass sorts by a single digit and relies on the previous pass's ordering surviving through ties. When two numbers share the current digit, a stable sort keeps them in the order they already had — which encodes all the lower digits sorted by earlier passes. An unstable inner sort would scramble those ties, destroying the work done so far, and the final array would come out wrong.
What is the time complexity of radix sort?
O(d · (n + k)), where n is the number of elements, d is the number of digits in the largest value, and k is the base (10 for decimal digits). Each of the d passes runs a counting sort in O(n + k). When d and k are bounded constants — for example, fixed-width 32-bit integers — this simplifies to O(n), which beats the O(n log n) lower bound of any comparison sort.
How does radix sort beat the O(n log n) comparison lower bound?
That lower bound only applies to sorts that learn about the data through pairwise comparisons. Radix sort never compares two numbers; it reads digits and drops each element into a bucket by its digit value. Because it extracts information a different way, the comparison-based lower bound simply doesn't govern it. It pays for that speed with O(n + k) extra space and a dependence on bounded digit width.
Can radix sort handle negative numbers or non-integers?
Not directly with the digit-extraction shown here, which assumes non-negative integers. For negatives, a common fix is to offset every value by the minimum so all keys become non-negative, then subtract it back at the end — or sort the absolute values and merge the negative and positive halves. Floating-point numbers require reinterpreting their bit patterns as sortable integers, which is possible but adds real complexity.
Is radix sort in-place?
No. Each counting-sort pass writes into a separate sortedArr output buffer of size n before copying back, plus a small count array of size k. That gives O(n + k) auxiliary space. If tight memory matters more than raw speed, an in-place comparison sort like heapsort or quicksort is the better fit despite the higher time complexity.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.