Ivan Kazmenko:
A seemingly easy way to provide the choice globally would be to
have an assignable SwapStrategy.default in std.algorithm... or
would that be a bad design decision to have such a global state?
With that I think there is no way to write a pure sort. Hopefully
someday the sort() will be pure. Generally global mutable state
is bad to write unittests, and to reason about code. So I don't
think Andrei will do that. It's not kosher.
Still, I think this is a problem in Phobos which should be
fixed.
In most implementations of quicksort (even middle-element, the
easiest to come up with), one expects it to perform in O(n log
n) with probability close to one, except on some artificially
constructed cases.
On a side note, I'm surprised that median-of-three (getPivot in
std.algorithm) fails at such a simple test, so I had something
new to learn there, too. If I just comment out the switch in
getPivot and "return mid" directly, it becomes fast enough in
this case.
Your case is a common one, so I think this problem should be
studied a little better. I suggest to write a little better
benchmark that shows the problem, and put it in Bugzilla. At
worst it will be closed with wontfix.
Another view at this is the following. As far as I know by
now, one of the points beyond D (and Phobos) design is to have
everything safe by default, but faster if you want it
explicitly and you know what you are doing.
Right, but I think that D Zen rule is mostly about things like
memory safety, etc.
So, why isn't TimSort the default?
Probably because someone thinks that "on average" the other sort
is faster.
In theory the other should be faster, because if you relax the
constraints of the sort being stable I think in theory you should
be able to write a little faster sorting algorithm (I don't know
if this is true).
Bye,
bearophile
