Re: [boost] [move][sort] Asymptotically optimal stable and in-place merging and sorting with no auxiliary memory

Subject: Re: [boost] [move][sort] Asymptotically optimal stable and in-place merging and sorting with no auxiliary memory
From: Ion Gaztañaga (igaztanaga_at_[hidden])
Date: 2016-03-24 07:14:02

On 24/03/2016 2:02, Steven Ross wrote:
> On Wed, Mar 23, 2016 at 6:52 PM Ion Gaztañaga <igaztanaga_at_[hidden]> wrote:
>
>> [Disclaimer, long e-mail, thank you for your attention]
>>
>> Hi to all,
>>
>> Some months ago I tried to gain interest from sorting experts about
>> implementing stable and inplace merge [O(N)] or sort [O(NlongN)]
>> algorithms that don't need additional memory.
>>
>> My main use case for these algorithms was lowering the complexity
>> guarantees of range insertion functions offered by flat associative
>> containers without any temporary allocation (the programmer does not
>> expect allocations when capacity() is big enough to hold the new
>> elements). On the other hand, I wanted those algorithms to be adaptive
>> so as to take advantage of the extra capacity already allocated by flat
>> containers.
>>
>
> I'm still confused why std::inplace_merge doesn't work for your use case;
> what's wrong with attempting to create a temporary buffer, and falling back
> to O(Nlog(N)) if it fails?  I still fail to see a practical advantage.

For desktop systems this is not a problem, unless you want to sort big 
ranges (like 1 GB in 32bit systems, you can run out of memory).

For flat containers, the issue is more related to class invariants where 
a vector/flat_map should never allocate if capacity() is enough, that's 
what the user expects.

Although I've only mentioned flat_xxx containers, my goal was to have a 
tool that could be useful in other contexts.

Another potential users are embedded developers that also don't like to 
allocate memory after initialization.

We could also try to allocate temporary storage, and if that fails, then 
the fallback could be NlogN to sort the input and O(N) to merge it 
instead of Nlog^2(N) when sorting and NlogN when merging.

Best,

Ion