Worst-case performance of quickSort / getPivot

[Andrei Alexandrescu]

On 11/16/13 6:42 PM, Xinok wrote:
> 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.

I am not so sure about that.

> Timsort already performs ideally in these cases, as I've demonstrated.

Yes, it is also my understanding that Timsort does well on almost sorted 
data. The issue is one does not know a priori what the distribution of 
the data is.

> 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.

We should have a "good unstable sort" in addition to the "good stable 
sort" we already have. Seeing this as a competition between quicksort 
and timsort would be the wrong frame.

Probably a good step forward would be to hook a sort benchmarking corpus 
to our unittests. What are the consecrated corpora?


Andrei