Randomness in built-in .sort

[dsimcha]

== 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.