I originally wrote this as a comment to the submission about the MonkeySort
http://news.ycombinator.com/item?id=4131217
I initially didn't find that write up very engaging, but then I realised it was actually related to work I did for my PhD, and so I thought I'd share that.
The proof that sorting a collection using comparisons requires a minimum of n.log(n) tests is well known. It simply uses the fact that there are n! possible orderings, and any comparison can only eliminate at most half (this is the crucial bit - I'll come back to it). Log(n!) is about c.n.log(n), so we might need that many comparisons. There are algorithms that are guaranteed to achieve that (shell sort, heap sort, etc.) and there are algorithms that usually perform that well and have a smaller constant (quicksort being the canonical example).
Fast forward.
Suppose we already have some information about the relative orderings of some of our items, and suppose there are now K possible linear orderings. How many comparisons might we need to make? The obvious answer is log(K), but that might not be possible. It may be that there is no selection of 2 items that lets us eliminate around half the remaining possible linear orderings.
Conjecture: Given a partially ordered set that is not already totally ordered, there exists a pair of elements a and b such that in a randomly chosen linear extension, the probability that a is above b is around 1/2 (in fact between 1/3 and 2/3 inclusive).
This means that given partial information, we can always find pairs of elements that eliminate around half (actually at least 1/3) of the remaining possible orderings. Thus, in theory, we can always sort in comparisons proportional to log(K) where K is the number of possible linear orderings consistent with the knowledge we have.
My PhD proved an infinitely large special case of the conjecture, showing that a plausible hiding place for counter-examples does not, in fact, harbor any.
Finding such pairs remains an open problem, and, in practice, unless your collection is already nearly totally ordered, it's usually quicker to discard partial information and start "from scratch".
