On Wednesday, 14 March 2012 at 03:55:31 UTC, Xinok wrote:
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.
Third update:
http://www.mediafire.com/?9jx07estd58wh2p
+ Added in-place sorting; Set template argument inPlace to true
+ Fixed CTFE compatibility issues
+ Vastly improved unittest
+ CTFE unittest will no longer stop compilation upon failure; It
will print a warning instead
+ Optimization: Recurse into smaller half, use tail call on
larger half
- CTFE test fails under DMD; Other compilers untested
I currently don't know why CTFE fails. The test performed at
compile-time is the exact same test that passes at runtime. The
code executes successfully but the array is not sorted correctly.
By implementing a tail call, in-place sorting should only use
O(log n) space on the stack, though at the cost of performance.
Sorting a random array of 1 million uints:
Phobos Unstable Sort - 132ms
Phobos Stable Sort - 2037ms
Proposed Stable Sort - 187ms
In-Place Stable Sort - 355ms
Sorting a random array of 1 million strings:
Phobos Unstable Sort - 1228ms
Phobos Stable Sort - 3516ms
Proposed Stable Sort - 1178ms
In-Place Stable Sort - 1422ms
Number of Comparisons on 1 million elements:
Phobos Unstable Sort - 24813812
Phobos Stable Sort - 25304078
Proposed Stable Sort - 19777088
In-Place Stable Sort - 21212726
