Counting sort
Do not compare items at all. Count how many times each key appears, then write the keys back out in order, each as many times as it was counted. Like sorting coins by dropping each into the slot for its value.
42725414
Press play or step forward to start.
1function countingSort(a) {2 if (a.length === 0) return;3 const min = Math.min(...a), max = Math.max(...a);4 const count = new Array(max - min + 1).fill(0);5 for (const x of a) count[x - min]++;6 let k = 0;7 for (let v = 0; v < count.length; v++) {8 for (let c = 0; c < count[v]; c++) a[k++] = v + min;9 }10}Keys: Space play or pause, ← → step. The URL always points at the frame you are on.
What it costs
| Case | Time | When |
|---|---|---|
| best | n + k | k is the key range, max − min + 1 |
| average | n + k | the input order never matters |
| worst | n + k | a wide key range: k can dwarf n |
| space | k | one counter per possible key |
Where it breaks
- A wide range of keys. It needs a counter for every value between the smallest and largest. Pick Spread out: 6 items need 93 counters, almost all of them zero.
- Anything that is not a small integer. Names, prices with decimals or whole records have no counter to drop into. It only works when keys can be used as array indexes.
- Records, not just numbers. This version rebuilds bare keys from the counts, so any data attached to them is lost. The stable version used inside radix sort turns counts into running totals and copies each record to its slot.