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.
