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.
