Worst-case performance of quickSort / getPivot

[Andrei Alexandrescu]

On 11/17/13 2:20 AM, Ivan Kazmenko wrote:
> 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.

That won't do with randomized pivot selection.

Andrei