On 10/13/18 9:31 PM, Jonathan M Davis wrote:
On Saturday, October 13, 2018 6:52:05 PM MDT Steven Schveighoffer via
Digitalmars-d-learn wrote:
You can't quick-sort a list. You can merge sort it, and it's O(nlgn).
I'll work on getting a sort routine into Phobos for it, but I don't know
what the appropriate location for it is, as a member or along-side
std.algorithm.sort.
Unless there's something about the implementation that's tied to the list
itself, I would think that it would make more sense to make it a generic
algorithm, then it will work with any non-random-access range, and it avoids
needing to reimplement it for similar circumstances. IMHO, it really only
makes sense to tie it to the container if the implementation itself needs to
be for some reason.
But that's just the thing -- merge sort *does* depend on the container
type. It requires the ability to rearrange the elements structurally,
since you merge the sets of items together. This requires making another
list from the original list, and ranges don't lend themselves to that.
One thing you *can* do is allocate an array beside the original
container, and move things back and forth. But this is not required if
you have a linked-list type which can simply be restructured without moving.
What I would do if I put it in std.algorithm is simply have an overload
for that specific type. Even that is kind of odd.
What I probably will do is make it a member of dlist and slist. At least
there it is limited to those items. I don't think dlist and slist have
the appropriate structural primitives to rearrange the list without
copying values around.
-Steve
