Regarding implementing a stable sort for Phobos

Xinok xinok at live.com
Thu Mar 15 13:20:58 PDT 2012


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


More information about the Digitalmars-d mailing list