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.
