11-Jul-2013 20:02, Joseph Rushton Wakeling пишет:
On 07/11/2013 05:17 PM, Andrei Alexandrescu wrote:
Unstable sort should be faster than stable sort. If I remember correctly (1) our
TimSort is indeed slower than quicksort on random numbers, (2) there is a
performance bug that makes our quicksort perform quadratically on data that's
essentially sorted but has one unsorted element at the end. Is that the case?
That's _exactly_ the case here. :-\
In such a case if inserting exactly one element into a sorted range you
may want to special case it to lowerbound + insert.
E.g. something like this:
auto idx = sortedRange.lowerbound(val).length;
//insert should be called on array backing that sortedRange
insert(sortedRange, idx, val);
Thanks for the clarification!
--
Dmitry Olshansky
