- Extract the digit at any decimal place using division and modulo.
- Explain why every digit pass must be stable.
- Trace bucket distribution and collection across multiple places.
- Relate d digit passes, n values, and b buckets to O(d(n + b)).
Sorting · Intermediate
Sort one digit.
Keep every prior decision.
Radix Sort repeatedly groups integer keys by ones, tens, hundreds, and higher places. Stable passes let each new digit refine the order without losing earlier work.
Mini example[ 21, 11, 12 ]
01
211112
ones02
112112
tens03
111221
sortedKey idea A digit pass must be stable: values sharing today's digit keep the order produced by all earlier passes.
Before you start
What you will learn
A clear finish line for the lesson, plus the small amount of knowledge you need before beginning.
- Integer division, modulo, and powers of ten
- Stable Counting Sort and frequency buckets
- Big O notation with multiple variables
01Understand02Visualize03Trace04Code05Complexity06Quiz07Challenge08Use cases
01 — The idea
Build order from right to left
How can sorting by the least important digit eventually produce complete numeric order?
407
Read one digit place
Start with ones. Missing higher digits behave like leading zeros, so 5 has tens digit 0 and hundreds digit 0.
21A→ 1 →21B
Distribute stably
Route values into buckets 0 through 9 while preserving their left-to-right arrival order inside each bucket.
1s10s100s
Collect and move left
Join buckets from 0 to 9, multiply the place by ten, and repeat until the largest shifted key has no digit left.
02 — Try it yourself
Watch stable digit passes build the order
Route each value into a digit bucket, collect buckets in order, and carry the stable result into the next place.
3–10 integers from -99 to 999
170ones digit 045ones digit 575ones digit 590ones digit 0802ones digit 224ones digit 42ones digit 266ones digit 6
0
empty
1
empty
2
empty
3
empty
4
empty
5
empty
6
empty
7
empty
8
empty
9
empty
·0·1·2·3·4·5·6·7
Formula: floor(key / 1) % 10Offset: 0Stable passes complete: 0
Digit reads0
Writes0
Passes0
Active value Active bucket Collected
Dry-run trace
Turn each animation into a written decision
| Step | Pass | Action | Value / digit bucket | Pass output | Writes |
|---|---|---|---|---|---|
| 0 | 1 · ones | Start digit pass | — | [170, 45, 75, 90, 802, 24, 2, 66] | 0 |
The highlighted row always matches the visualization above. Step forward to extend the trace.
03 — Read the code
From digit buckets to working code
Compare the same signed-key offset, stable base-10 pass, and growing place value across all four languages.
01export function radixSort(numbers) {02 if (numbers.some((value) => !Number.isSafeInteger(value))) throw new TypeError("Integers required");03 if (numbers.length === 0) return [];04 05 const minimum = Math.min(...numbers);06 const offset = minimum < 0 ? -minimum : 0;07 let array = numbers.map((value) => value + offset);08 const maximum = Math.max(...array);09 10 for (let place = 1; Math.floor(maximum / place) > 0; place *= 10) {11 const counts = Array(10).fill(0);12 for (const value of array) counts[Math.floor(value / place) % 10] += 1;13 for (let digit = 1; digit < 10; digit += 1) counts[digit] += counts[digit - 1];14 15 const output = Array(array.length);16 for (let index = array.length - 1; index >= 0; index -= 1) {17 const digit = Math.floor(array[index] / place) % 10;18 counts[digit] -= 1;19 output[counts[digit]] = array[index];20 }21 array = output;22 if (place > Math.floor(maximum / 10)) break;23 }24 return array.map((value) => value - offset);25}04 — Avoid the traps
Common mistakes
These bugs often produce an answer that looks almost right. Learn the symptom and the correction together.
Collecting a bucket out of order
Symptom: The ones pass looks correct, but later passes scramble values that share the same digit.
Correction: Treat every bucket as a queue. Preserve arrival order during both distribution and collection.
Ignoring leading zeros
Symptom: Short values such as 5 disappear or move after 50 during the hundreds pass.
Correction: Missing digits are zero. The expression floor(value / place) % 10 handles them automatically.
Applying decimal digits directly to negatives
Symptom: Modulo produces negative bucket indexes or an incorrect signed order.
Correction: This implementation adds one order-preserving offset so every working key is nonnegative, then removes it afterward.
05 — Check yourself
Check your understanding
Answer 4 questions, then reveal the reasoning. Your progress stays on this device—no account required.
0 of 4 answered
Answer every question to check your work.
06 — Mini game
Route the tens digit
Send each incoming value to the bucket matching its tens digit, including zero for missing tens.
Rule Use floor(value / 10) % 10. Keep values in arrival order inside each bucket.
Route 1700 picks
Incoming values · tens digit
170457590224
↓
What is the tens digit of 170?
07 — Use it wisely
Where Radix Sort fits
Fixed-width IDs
Large collections of bounded numeric identifiers can be ordered in predictable digit passes.
Strong fitTimes and dates
Normalized timestamps and date fields naturally decompose into bounded numeric positions.
Good fitString and byte keys
The same stable positional idea extends to fixed-width characters or bytes with a larger base.
Transferable patternCustom comparisons
Arbitrary objects, locale-aware text, and complex ordering rules do not map directly to digit buckets.
Use a comparison sortLesson progress
Finish this lesson with confidence
Use this private checklist to confirm what you learned. Progress stays only in this browser.
0 of 4 complete0%
Complete every checklist item to finish the lesson.