Regarding implementing a stable sort for Phobos

[Xinok]

On Tuesday, 13 March 2012 at 06:53:30 UTC, Chad J wrote:
> Hey, I'd love to see more sorting algorithms in phobos.  Being 
> stuck with one seems kind of... wrong.

Things like this are better left to 3rd party libs. Phobos 
already has two, a stable and unstable sort, which fulfill 99% of 
cases.

> 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.

Yes, it's possible because insertions are inexpensive in linked 
lists. However, it would be impractical to implement one at the 
moment because Phobos has no concept of linked lists (ranges 
wouldn't cover it).

> 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.

Insertion sort is one of the simplest sorts to write. I use it to 
optimize this stable sort as its super efficient at sorting small 
sublists. A natural merge sort would also work well in this case, 
but Timsort would work best. Timsort is also a natural merge 
sort, but it goes much farther than that.