(Improved) Benchmark for Phobos Sort Algorithm

[Peter Alexander]

On 18/12/10 4:46 PM, BCS wrote:
> Hello Craig,
>
>> It was brought to my attention that the quick sort has a very bad
>> worst case, so I implemented a simple fix for it. Now the worst case
>> (completely ordered) is the best case, and it only slows down the
>> general case by a small percentage. I thought to myself, "it can't be
>> this easy to fix quick sort". Does anyone see a flaw in this simple
>> fix? Performs much better than Phobos in completely random and
>> completely sorted data. Perhaps there is another case where it
>> doesn't do as well?
>>
>
> I think I've seen it stated as: If you know the implementation, you can
> always generate a pathological case for QSort.

That's not true for a randomized pivot point (unless you also happen to 
know the PRNG... and seed).