Worst-case performance of quickSort / getPivot

[Ivan Kazmenko]

On Sunday, 17 November 2013 at 03:58:58 UTC, Andrei Alexandrescu 
wrote:
> 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...

Actually, I was thinking about a two phase attack, and it is not 
at all unlikely.

0. Say, the Sorter presents a library quicksort solution.  It may 
be closed source, but can take comparison function as argument.

1. On the preparation phase, the Attacker uses the tricky 
comparison function described previously.  What's important is 
that, besides observing Theta(n^2) behavior once, he now gets a 
real array a[] such that this behavior can be reproduced.

2. On the attack phase, the Attacker does not need access to the 
comparison function.  He just feeds the array obtained on the 
previous step as plain data.

Ivan Kazmenko.