Randomness in built-in .sort

[Bill Baxter]

On Tue, Jan 6, 2009 at 12:16 AM, dsimcha <dsimcha at yahoo.com> 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.

Thanks for the pointer.  Actually when I said I "found" Oskar Linde's
sorting code, that really meant I found it sitting in my source tree
where I had incorporated it long ago after Oskar made it available.
So I just used that.

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

Actually, a function to sort multiple arrays in parallel was exactly
what I was implementing using .sort.  So that doesn't sound like a
limitation to me at all.   :-)

--bb