Non-comparison sorts need stronger input assumptions
Counting sort uses a bounded key range; radix sort processes digits using suitable stable passes; bucket sort distributes values under an assumed distribution. Their speed depends on those assumptions, not a general escape from all sorting costs.
fun countingSort(values: IntArray, maxKey: Int): IntArray {
require(maxKey in 0..1_000_000)
val counts = IntArray(maxKey + 1)
for (value in values) {
require(value in 0..maxKey)
counts[value]++
}
val result = IntArray(values.size)
var index = 0
for (key in counts.indices) repeat(counts[key]) { result[index++] = key }
return result
}
This integer-only form uses O(n+k) time and O(n+k) output-plus-workspace for key range size k. Sorting records stably requires prefix positions and careful placement, not just reconstructing keys.
Exercise
Test missing keys, repeats, empty input, and out-of-range values. Explain why allocating a count array for arbitrary 32-bit integers is impractical.
Check: radix complexity depends on digit count and radix; bucket worst cases can still be quadratic if one bucket receives nearly everything.