Actually, McIlroy's "killer adversary" will work just fine against typical randomized quicksort implementations! (It effectively constructs the data on the fly,

Actually, McIlroy's "killer adversary" will work just fine against typical randomized quicksort implementations! (It effectively constructs the data on the fly, guessing when the sorter is trying to find a pivot.) In that earlier HN discussion there was an extended (and frankly rather fruitless) debate between me and another poster about whether McIlroy's adversary can rightly be said to break randomized quicksort; that was basically terminological, and what is not in question is that if you take a typical randomized-quicksort implementation and feed it McIlroy's evil comparator, you will get order-n^2 performance.