Worst-case performance of quickSort / getPivot

[Xinok]

On Sunday, 17 November 2013 at 02:44:45 UTC, Vladimir Panteleev 
wrote:
> On Saturday, 16 November 2013 at 22:11:46 UTC, Xinok wrote:
>> And the results (last number is predicate calls):
>>
>> Current Unstable Sort  50ms  32783474
>> New Unstable Sort      69ms  21503542
>> Timsort                35ms  3905887
>
> For the record, I tried both SwapStragegy options with my data 
> (the data that got me to start this thread), and although 
> TimSort did fewer comparisons (predicate calls), it ran about 
> 20% slower.

Could you try running a benchmark on the same data using this 
instead?

https://github.com/Xinok/XSort/blob/master/unstablesort.d

My implementation of quick sort has some odd tweaks which makes 
it slower in some cases, but I've never invoked worst-case 
behavior by accident.