On Wed, Mar 23, 2016 at 6:52 PM Ion Gaztañaga
[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.