Loading algorithms…

Loading visualizer…

Algorithms/Sorting/Radix Sort

Radix Sort

Sort integers digit by digit using a stable counting sort. Each pass processes one digit place (ones, tens, hundreds, …) — achieving linear time O(d·(n+k)) without ever comparing values.

SortingNon-ComparisonStableLinear TimeInteger-only
Digit talliescount[d] operations
0
Writesplace + copy-back
0
Passes completedof total
0

Main + Counting + Output Arrays

Each pass: count the digits → prefix-sum → place by digit → copy back. Repeat for the next digit place.

default tallying placing writing sorted
Main arrayvalues: 0 – max(arr)
arrn = 16
10
21
32
43
54
65
76
87
98
109
1110
1211
1312
1413
1514
1615
Counting array10 slots · digits 0..9
Counting array · digits 0–9size = 10
00
01
02
03
04
05
06
07
08
09
Output scratch arraylength = n · filled right-to-left
Output scratch arraylength = n
—0
—1
—2
—3
—4
—5
—6
—7
—8
—9
—10
—11
—12
—13
—14
—15
1 / 0
Speed
Preset
n16
radix-sort.js
1function radixSort(arr) {
2 const max = Math.max(...arr);
3 let exp = 1; // 1, 10, 100, ...
4 while (Math.floor(max / exp) > 0) {
5 countingSortByDigit(arr, exp);
6 exp *= 10;
7 }
8}
9 
10function countingSortByDigit(arr, exp) {
11 const n = arr.length;
12 const output = new Array(n).fill(0); // scratch
13 const count = new Array(10).fill(0); // 0..9
14 
15 for (let i = 0; i < n; i++) {
16 const d = Math.floor(arr[i] / exp) % 10;
17 count[d]++; // tally digit
18 }
19 
20 for (let i = 1; i < 10; i++) {
21 count[i] += count[i - 1]; // prefix sum
22 }
23 
24 for (let i = n - 1; i >= 0; i--) {
25 const d = Math.floor(arr[i] / exp) % 10;
26 output[count[d] - 1] = arr[i]; // place
27 count[d]--;
28 }
29 
30 for (let i = 0; i < n; i++) {
31 arr[i] = output[i]; // copy back
32 }
33}

Algorithm Explanation

Radix sort is a non-comparison sorting algorithm for integers (and other keys with discrete structure). It processes the input digit by digit, from the least-significant digit to the most-significant. Each pass is a stable counting sort on one digit — and because counting sort is stable, the work done in earlier passes is preserved when later passes reorder the array.

⚙️ How It Works

  1. Find max to know how many digit-passes we need (d = ⌊log₁₀ max⌋ + 1).
  2. For each digit place (ones → tens → hundreds → …), run a stable counting sort on that digit. The counting sort has four sub-phases:
    • Tally — for each element, increment count[d] where d = (arr[i] / exp) % 10.
    • Prefix sum — turn tallies into end-positions (count[i] += count[i - 1]).
    • Place — walk the input right-to-left and write each element to output[count[d] - 1], decrementing count[d]. Walking right-to-left is what preserves stability.
    • Copy back — overwrite arr with output.
  3. After d passes, the array is fully sorted. Because each pass is stable and we process digits from least-significant to most-significant, earlier-pass orderings are respected by later passes.

🔢 Worked Example

// Pass 1: sort by ones digit
input: [170, 045, 075, 090, 002, 024, 802, 066]
by ones: [170, 090, 002, 802, 024, 045, 075, 066]
// Pass 2: sort by tens digit
by tens: [002, 802, 024, 045, 066, 170, 075, 090]
// Pass 3: sort by hundreds digit
sorted: [002, 024, 045, 066, 075, 090, 170, 802]

💡 Why LSD? MSD (most significant digit first) seems intuitive but requires recursion: once you bucket by the leading digit, you must recursively sort each bucket. LSD avoids this entirely — one full pass per digit place, no recursion, identical per-pass structure.

⚖️ Radix vs Comparison Sorts

Radix sort (this page)
  • O(d·(n + k)) — linear in n.
  • Stable.
  • Not in-place (O(n + k) extra).
  • Restricted to integer keys (or fixed-width digit-able keys).
  • Wins on large n with bounded key range.
Quick sort
  • O(n log n) avg, O(n²) worst.
  • Not stable.
  • In-place (O(log n) stack).
  • Works on any comparable type.
  • Best cache locality, fastest in practice on random data.
Merge sort
  • O(n log n) all cases.
  • Stable.
  • Not in-place (O(n) extra).
  • Great for linked lists, external sort, parallel sort.
  • Predictable worst-case behaviour.
Heap sort
  • O(n log n) all cases, in-place.
  • Not stable.
  • In-place (O(1) extra).
  • Worst-case guarantees with minimal memory.
  • Slower constant factor than quick/merge in practice.
←Previous Algorithm
Bubble Sort
SortingO(n²)
Next Algorithm→
Binary Search
O(log n)Searching

Radix sort is a non-comparison sort: it never compares two values directly. Instead, it exploits digit structure to bucket and stitch the array back together in O(d·(n + k)) time.