Regarding implementing a stable sort for Phobos

Chad J chadjoan at __spam.is.bad__gmail.com
Mon Mar 12 23:53:28 PDT 2012


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.

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.

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.


More information about the Digitalmars-d mailing list