Radix Sort — Algorithm Visualized
Learn radix sort — digit-by-digit stable counting sort, LSD passes, O(d(n+10)) complexity, interactive multi-pass visualizer.
Introduction
Radix sort sorts integers digit by digit (LSD: least significant first) using stable counting sort on each digit position. Handles large value ranges where plain counting sort would need too much memory.
Quick index
| # | Section |
|---|---|
| 1 | How it works |
| 2 | Interactive visualizer |
| 3 | Full implementation |
| 4 | Complexity analysis |
| 5 | Real-life examples |
1. How it works
Pass 1: sort by ones digit → stable
Pass 2: sort by tens digit → stable
...
Final array sortedStability at each pass preserves ordering from previous passes.
2. Interactive visualizer
Radix Sort — Step Visualizer
Stable counting sort on each digit — ones, tens, hundreds — LSD first.
Unsorted
Step 1 — Input array
const arr = [170, 45, 75, ...] // sort by each digit LSD → MSD
Radix sort uses stable counting sort on each digit position.
Time
O(d(n + 10))
Space
O(n + 10)
Stable
Yes
3. Full implementation
function radixSort(arr) {
const maxVal = Math.max(...arr)
for (let exp = 1; Math.floor(maxVal / exp) > 0; exp *= 10) {
countingSortByDigit(arr, exp)
}
return arr
}
function countingSortByDigit(arr, exp) {
const buckets = Array.from({ length: 10 }, () => [])
for (const num of arr) {
const digit = Math.floor(num / exp) % 10
buckets[digit].push(num)
}
arr.length = 0
for (const b of buckets) arr.push(...b)
}Function calls with output
// ── Demo calls — output shown on the right ──
const arr = [170, 45, 75, 90, 802, 24, 2, 66]
radixSort(arr) // → [2, 24, 45, 66, 75, 90, 170, 802]4. Complexity analysis
| Metric | Value |
|---|---|
| Time | O(d × (n + 10)) — d = digits |
| Space | O(n + 10) per pass |
| Stable | Yes |
5. Real-life examples
| Scenario | Why radix sort |
|---|---|
| Sorting phone numbers | Fixed 10 digits — sort by each digit position |
| Student ID sorting | IDs like 2024001234 — LSD radix on decimal digits |
| IP address sorting | Sort by octets — same digit-by-digit idea |
| Zip code batch processing | 5-digit codes — d=5 passes, linear per pass |
| Date sorting (YYYYMMDD) | Integer dates — radix sort without string parsing |
Employee ID sorting
10-digit employee IDs — LSD radix sort processes each digit position.
Index → value
HR batch — unsorted 3-digit IDs (demo scale).
Real-world implementation
function countingSortByDigit(arr, exp) {
const out = Array(arr.length).fill(0)
const count = Array(10).fill(0)
for (const n of arr) count[Math.floor(n / exp) % 10]++
for (let i = 1; i < 10; i++) count[i] += count[i - 1]
for (let i = arr.length - 1; i >= 0; i--) {
const d = Math.floor(arr[i] / exp) % 10
out[--count[d]] = arr[i]
}
return out
}
function radixSort(arr) {
let a = [...arr]
const max = Math.max(...a)
for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {
a = countingSortByDigit(a, exp)
}
return a
}Full working code for the scenario above.
Function calls with output
// ── Function calls with output ── const ids = [802, 170, 45, 90, 66]
Side output shows return value after each call — step through to trace execution.
Summary
Radix sort extends counting sort to large integers by processing fixed-width digits — linear in n for bounded d.
Next reads: Counting Sort · Quick Sort
Subscribe to my newsletter
Stay up to date and get notified when I share new contents.
No spam ever, unsubscribe anytime