Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

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[pi] < A[pj] 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 2k distinct executions of A on inputs of size n, and so there are at most 2k different possible permutations that A can generate as output. Since any possible ordering of the elements may appear in the input, 2k 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.

2014-06-17 11:58