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: Steven Ross (spreadsort_at_[hidden])
Date: 2016-03-23 21:02:31

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.