std.partition is fucked

[Andrei Alexandrescu]

Sean Kelly wrote:
> 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).

Yeah, I saw that fixed-size stack. I'm not sure whether that's 
responsible for much of its performance, one of these days I need to 
measure. My speculation is that the depth of the stack is small enough 
to not really contribute much to the running time.

Andrei