custom sorting of lists ?

[Steven Schveighoffer]

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