Worst-case performance of quickSort / getPivot

[Timon Gehr]

On 11/17/2013 02:14 PM, Ivan Kazmenko wrote:
> On Sunday, 17 November 2013 at 13:07:40 UTC, Timon Gehr wrote:
>> On 11/17/2013 02:07 AM, Ivan Kazmenko wrote:
>>> The random pick fails in the following sense: if we seed the RNG,
>>> construct a killer case, and then start with the same seed, we get
>>> Theta(n^2) behavior reproduced.
>>
>> Hence, in no sense. This does not perform independent uniform random
>> picks.
>
> Not at all.  There is a number of situations where you want your program
> to use RNG, but it is also important for the result to be reproducible.
> In such cases, you typically store the RNG seed for re-use.
>
> Of course there are also many cases where you don't need reproducibility
> guarantees, and there, the attack is useless.
>
> Ivan Kazmenko.

One can't say random picking is bad because one can use some other 
(deterministic) pivot selection algorithm instead which is bad. If you 
need deterministic reproducibility guarantees, then random picking is 
useless.