Regarding implementing a stable sort for Phobos

[Xinok]

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.

Sorting a random array of 1 million uints:
Phobos Unstable Sort - 132ms
Phobos   Stable Sort - 2037ms
Proposed Stable Sort - 187ms

Sorting a random array of 1 million strings:
Phobos Unstable Sort - 1228ms
Phobos   Stable Sort - 3516ms
Proposed Stable Sort - 1178ms

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

You can download the preliminary lib here:
http://www.mediafire.com/?ux49x30dj483dqg