"in" everywhere

[Andrei Alexandrescu]

On 10/9/10 12:12 CDT, Peter Alexander wrote:
> On 9/10/10 5:25 PM, Andrei Alexandrescu wrote:
>> 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
>
> Could you elaborate? I don't see how you lose in-place sorting with the
> random and middle selection cases.

You just take median-of-some and also sort those elements right away 
before returning the pivot. It's a minor improvement.

Andrei