I've discovered a number of cases in which the unstable sort in std.algorithm performs very poorly. I'll provide the simplest example I have.
import std.stdio, std.algorithm, std.range, std.datetime;
void main(){
uint[] arr;
arr.length = 1024 * 1024;
foreach(i, ref v; arr) v = i;
swapRanges(arr[0..$/2], arr[$/2..$]);
StopWatch sw;
sw.start();
sort(arr);
sw.stop();
writeln(sw.peek.seconds, " seconds");
}
This case takes 28 seconds on my PC. The problem can be solved by falling back to a heap sort or shell sort after so many recursions. Slow cases like these have possible security implications.
Comment #1 by github-bugzilla — 2013-12-15T09:02:02Z