CMP.11:5.2 - Bound comparison sorting and identify its escape

Sort n distinct opaque keys, with their order available only through pairwise comparisons. A comparison has two possible outcomes. The n! possible input orders require different output permutations, so a correct decision tree needs at least n! leaves. A binary tree of height q has at most 2^q leaves. Thus the worst case needs at least ceil(log2(n!)) comparisons, which grows as Ω(n log n).

This bound is about comparison sorting. If each key is an integer in 0..K-1 and direct array indexing is an allowed elementary operation, count occurrences in K counters and emit keys in index order. That construction uses O(n+K) counter/access operations and corresponding output work. It escapes the comparison bound by observing the encoding through indexing. Large K, long integers or a requirement to preserve distinct record identity can change its storage and reconstruction costs.

A practical consequence is to compare representations and access before spending effort trying to make an ordinary comparison procedure sort arbitrary distinct keys in fewer than order n log n comparisons. If comparisons themselves are expensive, a matching comparison count still leaves their internal cost to reduce.