On Tue, Jan 6, 2009 at 12:16 AM, dsimcha <[email protected]> wrote: > == Quote from Andrei Alexandrescu ([email protected])'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
