Regarding implementing a stable sort for Phobos

[Xinok]

On Tuesday, 13 March 2012 at 08:37:06 UTC, deadalnix wrote:
> I have a radix sort (that need some rework to be phobos 
> quality) and a smoothsort (that could be included in phobos).

Would you mind sharing your smoothsort? I haven't implemented one 
myself and I'd love to test it out.
Radix sort, on the other hand, is not a comparison sort. You'd 
have to rewrite it for every possible element and container type.

> I have a sort for ForwardRange, but it is O(n²) and unstable. 
> However, it is in place.

I posted one a few days ago myself - 
http://forum.dlang.org/thread/cmipnxrarexjgnrdqlvr@forum.dlang.org

> I don't think we should allocate behind one's back, so merge 
> sort should be an option, unless called explicitely.

When it comes to stable sorts, merge sort is the best choice. I 
found tree sort to be quite slow (using RedBlackTree in 
std.container), and a stable quick sort is still slower than a 
merge sort. So I guess that'd mean an in-place merge sort. I've 
implemented one which was 3x slower than quick sort. Allocating 
even a small amount of space makes a big difference.

> smoothsort is a good solution for that. radix is also guarantee 
> to be O(n). Insertionsort is quite risky, because it can ends 
> up in O(n²) very easily.