A **comparison-based sorting algorithm** can't see anything about the elements in its input array except the outcome of comparisons (i.e., x < y or x > y, assuming all elements are distinct). We can model a comparison-based algorithm by putting it in a straightjacket where its only access to the input array is through procedure calls of the form `compare(i,j)`, which returns true if and only if `A[i] < A[j]`. The output of the algorithm is a permutation p of 1..n such that A[p_{i}] < A[p_{j}] whenever i < j.

It's not hard to show that any deterministic comparison-based sorting algorithm takes Ω(n log n) comparisons to sort. Fix some algorithm A, and suppose that A performs at most k comparisons on inputs of size n. We can summarize all possible executions of A by writing down the outcome (true or false) of each of these comparisons. Note that we do *not* have to keep track of *which* elements are compared at each step; we can deduce this by simulating A given the output of the previous comparisons. It follows that there are at most 2^{k} distinct executions of A on inputs of size n, and so there are at most 2^{k} different possible permutations that A can generate as output. Since any possible ordering of the elements may appear in the input, 2^{k} had better exceed n!. This can only happen if k >= lg(n!) = Ω(n log n).

# 1. Beating the bound

The first thing to ask if you see a lower bound like this is how to beat it. In this case, if we can drop the restriction to just performing comparisons, we can get the time to sort down to O(n) in some cases. An example is Counting_sort or Radix_sort with small enough keys.