Randomness in built-in .sort

[Don]

dsimcha wrote:
> == Quote from Andrei Alexandrescu (SeeWebsiteForEmail at erdani.org)'s article
>> dsimcha wrote:
>>> On another note, it would be nice if std.algorithm implemented a stable O(N log N)
>>> sort, like a merge sort.  Right now, IIRC it uses an interesting stable swapping
>>> algorithm on top of a quick sort for O(N log^2 N) performance.  This is good when
>>> space is tight, but I think in most cases a merge sort is better as a stable sort.
>> I agree. I didn't have the time to implement a very good stable sort,
>> but I also think the extra slowness is not critical. If anyone comes
>> with a better implementation, I'd be glad to integrate it.
>> Andrei
> 
> You could try the merge sort implementation from my dstats library at
> http://dsource.org/projects/dstats/browser/trunk/sort.d.  This is very heavily
> tested and optimized because some important higher level dstats functionality
> depends on it.  You'd basically just have to add a template parameter to allow a
> user-provided swap function to make it conform to std.algorithm conventions.
> Obviously, since it's by its nature a stable sort, you don't really need the
> swapStrategy alias.
> 
> One thing to note, though, is that this function is designed to allow for sorting
> parallel arrays in lockstep by simply passing them in as additional parameters.
> This adds some complexity to the implementation.  Also, it uses the TempAlloc
> region allocator for temp space.  You could put this in Phobos too (This allocator
> was actually your idea a while back, though you called it a SuperStack), or you
> could change the temp space allocation to simply use the regular heap allocation
> scheme.

I want TempAlloc in dcore! Eventually, anyway.