On Saturday, 10 June 2017 at 10:59:24 UTC, Steven Schveighoffer
wrote:
I wrote it like this, which confirms that it's indeed
bringToFront (I tried your getTransitionIndex function, but
that didn't change timings at all):
void insertionSort(alias Less, Range)(Range r)
if (hasLength!Range && isRandomAccessRange!Range &&
hasSlicing!Range)
{
foreach (immutable i; 1 .. r.length)
{
auto ubElem = i - r[0 ..
i].assumeSorted!Less.upperBound(r[i]).length;
r[ubElem .. i+1].rotateRight;
}
}
Taking the length of upperBound is a great move! ;-)
On my mac, it's completing in about 4.4 seconds, whereas the
C++ version completes in around 3.
On my machine, I am getting the same performance even without
resorting to memmove. Using getTransitionIndex directly, however,
leads to a neglectable improvement (about 2.7 vs. 2.8 seconds),
here.
