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
