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

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 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