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
