Every sort you have seen compares pairs of elements — and no comparison sort can beat n·log n. Counting sort never compares anything: it just tallies how many of each value there are, then reads them out in order. When the values live in a known range, it sorts in linear time — and it is the perfect fit for I-13’s bounded array, whose length is fixed and known.
THE TECHNIQUE tally, then read the tallies back out
Make a bucket for every possible value. Scan the input once, adding one to a value’s bucket. Then walk the buckets low to high, emitting each value as many times as it was counted. No element is ever compared to another. live demo
HISTORY & CREDIT a 1954 thesis that beat the n log n barrier
Told as if all sorting is comparison and bounded by n log n — always true only when you insist on comparing. cited
1954 · Harold H. Seward, in his MIT master’s thesis, describes counting sort and radix sort — sorting by distribution, not comparison. the barrier · any sort that only compares needs Ω(n log n) comparisons (the decision-tree bound). Counting sort steps outside the model: it reads values as addresses, so the bound does not apply. the cost · O(n + k) time and O(k) space for values in 0..k — unbeatable when k is small, wasteful when k is huge. It is the engine inside radix sort.
Not a faster way to compare — a way to sort without comparing at all. outside the box
RECOMMEND FOR I-13 the sort the bounded array was made for
A tally array (one bucket per value) and an output array — both bounded, both fixed length. It runs and sorts:
def tally(I c, I a, I i, I n) {
if i >= n { -> c }
c[a[i]] <- c[a[i]] + 1 // count value a[i]
-> tally(c, a, i + 1, n)
}
// then emit each value c[v] times, low to high
$ i13 run counting.i13 # sort [4,2,7,2,0,5,2,9]
first = 0 third = 2 last = 9 # -> 0,2,2,2,4,5,7,9
Recommend:nothing new — and of all the array darts, this is the most natural fit. Counting sort needs an array whose size is a known bound (the value range) — which is exactly what I-13’s array is: bounded, fixed-length, checked. Where quicksort (045) strained against the language, counting sort fits it like a glove: no comparisons (so no ordering machinery), just indexed writes into a bounded table. The arc: the array cleared the aggregate wall; the algorithm that suits a bounded array best is the one that sorts by counting into it. Feature and use, made for each other.