std.partition is fucked

Sean Kelly sean at
Wed May 13 09:37:46 PDT 2009

Andrei Alexandrescu wrote:
> The performance of std.sort is back to normal - still slower than the 
> built-in sort (but not by orders of magnitude), probably because bumping 
> ranges is at a disadvantage.

The built-in sort uses an internal stack rather than recursion, which 
makes its performance on a best-case dataset hard to beat.  I finally 
satisfied myself by having a constant time overhead vs. the built-in 
sort for best-case and beat it by polynomial time for worst-case (the 
built-in sort doesn't adapt to worst-case datasets very well).

More information about the Digitalmars-d mailing list