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
