"in" everywhere

[Peter Alexander]

On 9/10/10 4:53 PM, bearophile wrote:
> Andrei:
>
>> Currently std.algorithm.getPivot picks the middle of the range as the
>> pivot, but I made it modular such that it can be improved in a number of
>> ways (i.e. randomized, median-of-3, median-of-5, etc).
>
> Isn't median of 3 a better default?
>
> Bye,
> bearophile

There is no "best". They are all trade-offs between the time taken to 
select the pivot and the suitability of the pivot.

Middle - Fastest, not very good
Median-of-3 - Slower, but slightly better
Median-of-5 - Slower still, but even better

Randomized - Speed depends on the random number algorithm. Suitability 
is random, so could be good, could be bad, but on average it's good 
enough. Has the added quality that it's practically impossible to devise 
worst-case input for it (you'd need to know the generator and seed), 
whereas for the other 3, a malicious user could provide data that gives 
you O(n^2) complexity.