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