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.
