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

On Monday, 15 October 2018 at 13:39:59 UTC, Steven Schveighoffer wrote:
>
> 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.

Doesn't this just mean a new special kind of range is needed to be defined?

On 10/17/18 2:03 PM, Carl Sturtivant wrote:
> On Monday, 15 October 2018 at 13:39:59 UTC, Steven Schveighoffer wrote:
>>
>> 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.
> 
> Doesn't this just mean a new special kind of range is needed to be defined?
> 

I don't think it fits into range primitives. Basically, I need to rearrange one element from one place to another in O(1) time (and without actually moving/copying the data).

This really just is a linked-list special feature. One thing to note is that in a range of T, this move has nothing to do with the T.

-Steve

On Wednesday, 17 October 2018 at 19:02:00 UTC, Steven Schveighoffer wrote:
> On 10/17/18 2:03 PM, Carl Sturtivant wrote:
>> On Monday, 15 October 2018 at 13:39:59 UTC, Steven Schveighoffer wrote:
>>>
>>> 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.
>> 
>> Doesn't this just mean a new special kind of range is needed to be defined?
>> 
>
> I don't think it fits into range primitives. Basically, I need to rearrange one element from one place to another in O(1) time (and without actually moving/copying the data).
>
> This really just is a linked-list special feature. One thing to note is that in a range of T, this move has nothing to do with the T.
>
> -Steve

If we imagine an Ordered Range being a finite Range of some kind with the additional property that its values are ordered (--- exact definition needed ---). And work with Ranges of Ordered Ranges, can't we then sort by starting with a Range of single element Ranges (which are automatically ordered), and then pairwise merge repeatedly, i.e. get the next two elements (which are ordered ranges) and merge them & repeat, producing a Range of Ordered Ranges with half as many elements --- this is what I meant by pairwise merging --- and apply that pairwise merge repeatedly to the original range. I'm speculating intuitively, but it does look like there exists a possible extension of the notion of Range that would do the job.

On Friday, 19 October 2018 at 17:40:59 UTC, Carl Sturtivant wrote:

> If we imagine an Ordered Range being a finite Range of some kind with the additional property that its values are ordered (--- exact definition needed ---)...

There's already a SortedRange: https://dlang.org/phobos/std_range.html#.SortedRange

On Friday, 19 October 2018 at 17:53:58 UTC, Stanislav Blinov wrote:
> On Friday, 19 October 2018 at 17:40:59 UTC, Carl Sturtivant wrote:
>
>> If we imagine an Ordered Range being a finite Range of some kind with the additional property that its values are ordered (--- exact definition needed ---)...
>
> There's already a SortedRange: https://dlang.org/phobos/std_range.html#.SortedRange

That's nice. So perhaps all this can be done in using the existing machinery in Phobos.

On 10/19/18 3:58 PM, Carl Sturtivant wrote:
> On Friday, 19 October 2018 at 17:53:58 UTC, Stanislav Blinov wrote:
>> On Friday, 19 October 2018 at 17:40:59 UTC, Carl Sturtivant wrote:
>>
>>> If we imagine an Ordered Range being a finite Range of some kind with the additional property that its values are ordered (--- exact definition needed ---)...
>>
>> There's already a SortedRange: https://dlang.org/phobos/std_range.html#.SortedRange
> 
> That's nice. So perhaps all this can be done in using the existing machinery in Phobos.
> 

Again, the benefit of linked lists here is we don't have to actually move any data, we are just rearranging pointers.

We can certainly create a mergesort routine that works with any data types, as long as it has scratch space to move the data around. But that isn't as effective or efficient as a dedicated linked-list routine.

-Steve