Le 13/03/2012 07:53, Chad J a écrit :
On 03/13/2012 02:31 AM, 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.
...
Hey, I'd love to see more sorting algorithms in phobos. Being stuck with
one seems kind of... wrong.
I have a radix sort (that need some rework to be phobos quality) and a
smoothsort (that could be included in phobos).
If the range is a linked list, shouldn't it be possible to do a merge
sort with optimally in-place and use no extra memory whatsoever? I know
it can be done in-place, but I've never benchmarked it. I wonder if it's
worth considering, and how it would compare against array-based merge
sort with allocations and such.
I have a sort for ForwardRange, but it is O(n²) and unstable. However,
it is in place.
I don't think we should allocate behind one's back, so merge sort should
be an option, unless called explicitely.
Although it's probably out of your scope right now, I'd like to see
insertion sort some day. I would use it for things like broadphase
sorting in collision detection (that is, you sort everything by say, x
coordinates first, and then you can walk through the whole simulation
from left-to-right and have very few things to check collisions for at
each point). Since the ordering of the objects in the simulation is
unlikely to change much between frames, it will be almost entirely
sorted each time. I have to imagine insertion sort would be awesome at
that; nearly O(n). Maybe if it hits more than log(n) nonlocal insertions
it would bail out into a merge sort or something.
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.
