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.
