Worst-case performance of quickSort / getPivot

Xinok xinok at live.com
Sat Nov 16 18:42:25 PST 2013


On Sunday, 17 November 2013 at 00:56:46 UTC, Andrei Alexandrescu 
wrote:
> On 11/16/13 4:18 PM, Chris Cain wrote:
>> You have not shown how much faster it might be (it could be
>> only 1% faster) nor how much work it would take to discover 
>> (even an
>> ideal pivot choice for quicksort actually cannot be as fast as 
>> Timsort
>> on an already sorted sequence, and quicksort is not an 
>> appropriate
>> algorithm for accepting presorted subsequences).
>
> There are well known tweaks to quicksort that make it operate 
> well on sorted or almost sorted sequences.

If you tweak for one scenario, you're only losing in other 
scenarios. Timsort already performs ideally in these cases, as 
I've demonstrated. Rather than optimizing quicksort for cases in 
which Timsort will still be the victor, we should optimize for 
those cases in which quicksort is already faster.


More information about the Digitalmars-d mailing list