Quadratic time to sort in a simple case?

[bearophile]

Ivan Kazmenko:

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


> The question is rather predictable, really: what is the 
> guaranteed-n-log-n replacement for sort in the standard 
> library?  I've found the following way...
> 	sort !("a < b", SwapStrategy.stable) (a);

That uses the TimSort that contains the optimization you look for.


> ...but it forces to specify the redundant "a < b" and looks a 
> bit clumsy for an everyday sort() call.

Then try to define an alias (untested):

alias mySort = sort!("a < b", SwapStrategy.stable);

Bye,
bearophile