Bug 2966 – std.algorithm.sort Slower than Selection Sort

I noticed some code I wrote using std.algorithm.sort was really slow, so I tested it against the builtin sort and a quick and dirty selection sort I wrote. (Yes, I used a selection sort just to show how severe this actually is.) Here's the test program: import std.stdio, std.algorithm, std.perf, std.random; void main() { enum N = 100_000; uint[] foo = new uint[N]; // This isn't a corner case bug. There should be almost no ties here. foreach(ref elem; foo) { elem = uniform(0U, 4_000_000_000U); } auto bar = foo.dup; scope pc = new PerformanceCounter; pc.start; std.algorithm.sort(bar); pc.stop; writeln("std.algorithm: ", pc.milliseconds); bar[] = foo[]; pc.start; selecSort(bar); pc.stop; writeln("Selection sort: ", pc.milliseconds); bar[] = foo[]; pc.start; bar.sort; // Builtin. pc.stop; writeln("Builtin sort: ", pc.milliseconds); } void selecSort(uint[] data) { foreach(i; 0..data.length) { uint minI = i; foreach(j; i + 1..data.length) { if(data[j] < data[minI]) { minI = j; } } swap(data[i], data[minI]); } } And the timings: std.algorithm: 5708 Selection sort: 4029 Builtin sort: 21

Fixed in 2.031.