One semi-interesting thing here is that the "killer adversary" described on that page requires knowing that the algorithm you're trying to exploit is quicksort.
Long ago, I wrote adversaries that attempt to force _any_ algorithm that is extracting a partial or total order from data to approach their worst case.
These adversaries, like McIlroy's adversary, sits in the compare() function, but it asks itself "what answer can I give, consistent with the data so far, to force the algorithm to ask me the largest number of subsequent questions?"
For non-introspective quicksorts this will be O(n^2), but it should also bring out the worst constant factors in O(n\logn) worst case time algorithms.
Very interesting writeup. How did you determine the number of topological sortings for your "Yes" and "No" examples? I'm getting 360 and 144, rather than 120 and 48 that you wrote.
Long ago, I wrote adversaries that attempt to force _any_ algorithm that is extracting a partial or total order from data to approach their worst case.
These adversaries, like McIlroy's adversary, sits in the compare() function, but it asks itself "what answer can I give, consistent with the data so far, to force the algorithm to ask me the largest number of subsequent questions?"
For non-introspective quicksorts this will be O(n^2), but it should also bring out the worst constant factors in O(n\logn) worst case time algorithms.
I did some experiments: http://nicknash.me/2012/07/31/adversaries/
A proper reference is the Kahn's "Sorting and Entropy", IIRC.