Radix sort
Sort by the last digit, then by the next one, and so on, always keeping ties in the order the last pass left them. After the final digit everything is in order, without ever comparing two items.
53728914663512
Press play or step forward to start.
1function radixSort(a) {2 const max = Math.max(0, ...a);3 for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {4 const buckets = Array.from({ length: 10 }, () => []);5 for (const x of a) buckets[Math.floor(x / exp) % 10].push(x);6 let k = 0;7 for (const bucket of buckets) {8 for (const x of bucket) a[k++] = x;9 }10 }11}Keys: Space play or pause, ← → step. The URL always points at the frame you are on.
What it costs
| Case | Time | When |
|---|---|---|
| best | d · n | d is the number of digits in the largest key |
| average | d · n | the input order never matters |
| worst | d · n | one huge key adds a pass for everyone |
| space | n + 10 | every item sits in a bucket during a pass |
Where it breaks
- Every pass must be stable. The tens pass only works because items with the same tens digit stay in ones order. Pick Shared digits and watch 31, 32 and 33 keep the order the first pass gave them.
- One long key slows everything. The number of passes comes from the largest key. A single 1,000,000 in a list of small numbers makes every item go through seven passes.
- Negative numbers and decimals. Digits of −5 or 2.5 do not drop into buckets 0 to 9 the way this code expects. Real implementations shift negatives or sort the raw bits instead.