Non-comparison Sorting

The Ω(n log n) lower bound applies to algorithms that learn order only through comparisons. Extra knowledge about key structure enables other approaches.

Counting sort

For integer keys in a known range of size k, count occurrences and reconstruct the order. Time is Θ(n + k) and auxiliary space is Θ(k) or Θ(n + k) for a stable output-producing form. It is unattractive when the range is enormous relative to the input.

Radix sort

Radix sort processes keys digit by digit using a stable sub-sort. With d digits and radix k, a conventional bound is Θ(d(n + k)). Correctness of least-significant-digit radix sort relies on the stability of every digit pass.

Bucket sort

Bucket sort distributes values into intervals, sorts within buckets, and concatenates them. Expected performance depends on the stated input distribution; a poor distribution can concentrate most elements in one bucket.

Use these methods only when domain assumptions and memory costs are explicit.

Exercises

1. Write stable counting sort that retains associated records.
2. Explain why an unstable digit sort can invalidate LSD radix sort.
3. Compare counting sort with QuickSort when k is much larger than n.