That [SwapStrategystable] uses the TimSort that contains
the optimization you look for.
alias mySort = sort!("a < b", SwapStrategy.stable);
Thank you, these are good for now.
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?
Consider a sorted array. Append an element that is less than
all the previous elements. Then sort the array again by the
sort function from std.algorithm.
If you know that, then don't do a sort. Make some free space in
the array, shift the items, sort just the first part with a
slice.
That behavior isn't always easy to predict.
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.
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. In this particular case, that
would mean having a worst-case O(n log n) sort, and/or a stable
sort, by default - but with the opportunity to switch to the
(time-wise and stability-wise) unsafe quicksort if you really
need the extra speedup and know what you are doing. So, why
isn't TimSort the default?
The one reason I can imagine is that then D would suffer in
language comparisons which just take the most easy-to-use
"default sort" and don't care about the extra features it got.
Are there any other?
Ivan Kazmenko.
