Boost logo

Boost :

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.



Boost list run by bdawes at, gregod at, cpdaniel at, john at