On Saturday, 16 November 2013 at 23:40:39 UTC, Andrei
Alexandrescu wrote:
This is in response to what? Are you trying to talk me out of
the pigeonhole principle?
...
I understand and appreciate that Timsort is a nicely optimized
algorithm. This has nothing to do with it doing more work than
an unstable sort that is just as nicely optimized.
At the end of the day whatever stable sorting algorithms are
out there, their set is included in the set of all sorting
algorithms. In order to preserve stability, stable sorting
algorithms need to do nonnegative extra work.
Andrei
I think it's more complicated than that. Let's assume for a
moment that you've proven that such an unstable sort must exist
that is faster (I'm not convinced that it necessarily must take
extra work to maintain stability). 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). If it takes 2 years to
come up with an unstable sort faster than Timsort, then it seems
like a long time to be using something that isn't the best that
we currently have. Especially if D is to be used in benchmarks
against other languages.
Timsort is implemented now and has no real cost to use as
default. If, at some point, an unstable sort is discovered that
is faster on average than Timsort AND (extremely important) it
has no potential for an attacker to be able to choose a sequence
to sort that causes poor performance, then unstable could be
switched back as the default at some point.
Right now, this could, in fact, cause a security hole (DOS-type
attack) depending on how it is used. I think it's better to use a
safer default in this case, even if we could make it faster than
Timsort somehow.
