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/[email protected]
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.
