THE BUCKET SORT scatter into bins, gather in order — when you know the range
Bucket sort (and its cousin counting sort) trades comparisons for knowledge of the range: scatter each value into a bin by its value, then read the bins back in order. When the keys are integers in a small known range, this is O(n + k) — linear — and it is exactly how a bank once sorted checks into pigeonholes. Its limit is the mirror of its strength: you must know the range, and a wide sparse range wastes bins. Here the values 4,2,7,1,5,2 scatter into count-bins and gather back as [1,2,2,4,5,7] — sorted, without a single comparison.
THE TECHNIQUE scatter by value into bins, gather in order — O(n+k), no compares
The demo bucket-sorts [4,2,7,1,5,2] by counting into bins and reading them back in order: live demo
HISTORY & CREDIT bucket / counting sort · the pigeonhole
“Linear-time sorting is impossible.” — it is, if you know the range: scatter into bins, gather in order, O(n+k). cited
the scatter · drop each value into the bin for its value (or value-range). the gather · read the bins in order — sorted, no comparisons; O(n+k). the limit · you must know the range; a wide sparse range wastes bins.
Values pigeonholed by their own value and read back in order — linear sorting, when you know the range. resource
RECOMMEND FOR I-13 the binned sort, on the compiler
On the canonical compiler, [4,2,7,1,5,2] scatters into count-bins and gathers as [1,2,2,4,5,7] (lo 1, hi 7):
$ i13 run or_bucketsort.i13 # scatter into bins, gather in order
RUN OK · 681 step(s) · peak stack 14 · call depth 11
lo = 1 hi = 7
sorted12 = 1 -- [1,2,2,4,5,7]
Recommend as a NULL — resource, range-bought. Bucket/counting sort achieves linear time by exploiting a known key range (B40) via a value-indexed representation (B44) — the same comparison-free trick as radix (dart 506). No new invariant. NULL — the pigeonhole sort.