Regarding implementing a stable sort for Phobos

[deadalnix]

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.