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

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.

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