On 11/16/13 5:07 PM, Ivan Kazmenko wrote:
The above is just my retelling of a great short article "A Killer Adversary for Quicksort" by M. D. McIlroy here: http://www.cs.dartmouth.edu/~doug/mdmspe.pdf
Nice story, but the setup is a tad tenuous (albeit indeed theoretically interesting). For starters, if the attacker has a hook into the comparison function, they could trivially do a lot worse...
Andrei
