Worst-case performance of quickSort / getPivot

[Vladimir Panteleev]

On Sunday, 17 November 2013 at 03:14:41 UTC, Xinok wrote:
> 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.

Sorry for the late reply - my access to my home PC was spotty in 
the past week.

I wasn't entirely correct in the parent post - I didn't test 
things in the same way as the original problem, since I 
originally encountered it while using multiSort. multiSort can't 
use stable sort, because "stable $(D partition3) has not been 
implemented yet". If I hack multiSort to use TimSort instead of 
QuickSort, the program finishes quickly.

I reran the test in the same way as in the parent post, incl. 
with unstableSort. Here are the results:

SwapStrategy.unstable: 560576749 comparisons, 4796076 ticks
SwapStrategy.stable  : 340617464 comparisons, 5757974 ticks
unstableSort         : 573916901 comparisons, 5255061 ticks