"in" everywhere

[Peter Alexander]

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.