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:24:37

On 24/03/2016 12:14, Ion Gaztañaga wrote:
> 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.
>

I forgot to mention that Boost.Container supports C++03 so I would need 
to write my own inplace_merge version (which maybe I should). You might 
be interested in the mergesort implementation used for tests as I think 
it's faster than many std::stable_sort implementations.

Best,

Ion