Regarding implementing a stable sort for Phobos

[Xinok]

On Tuesday, 13 March 2012 at 18:32:27 UTC, Xinok wrote:
> On Tuesday, 13 March 2012 at 06:32:01 UTC, Xinok wrote:
>> I've been playing with sorting algorithms a lot in recent 
>> months, so I want to implement a *working* stable sort for 
>> Phobos which is broken at the moment. I have a working library 
>> and I'm still adding to it. It's much more complex than a 
>> simple merge sort, being over 300 lines of code at the moment.
>
> I've implemented slicing which has improved benchmarks quite a 
> bit.
>
> It still uses O(log n log n) space. I modified the code to 
> allocate up to 1KiB on the stack, and use the heap for anything 
> larger. I simply marked the entry sort function as @trusted. 
> The non-slicing code is still in the lib but disabled. I've yet 
> to add contracts, documentation, and a unittest.
>
> I won't be adding optimized code for arrays utilizing pointers 
> as I expect the performance gain to be as little as 10%.

A second update:
http://www.mediafire.com/?gqejl17ob1ywyat

I removed the code without slicing from the lib, though I still 
retain a copy.
I added 3 unittests: A basic sort test, a stability test, and a 
CTFE test.
I added a few asserts which have helped me discover bugs in the 
past.
I only added basic documentation. I've found it difficult to 
explain to others how an in-place merge sort works, so I didn't 
bother.

I've ran the code through several tests. It works, it's stable, 
and it consistently gives good performance. So for the all 
important question: Does anybody want to implement it in 
std.algorithm for me? I've looked at the code in std.algorithm, 
and all I can tell is that sortImpl is a recursive function. I 
have no idea what it's doing or what I need to change.