Quadratic time to sort in a simple case?

[Ivan Kazmenko]

> 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.