"in" everywhere

[Andrei Alexandrescu]

On 10/9/10 11:23 CDT, Peter Alexander wrote:
> 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.

Also: in-place sorting for the median cases.

Andrei