custom sorting of lists ?

[Carl Sturtivant]

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.