dsimcha wrote:
== Quote from Andrei Alexandrescu (seewebsiteforem...@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.
