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-24 20:57:59

On Thu, Mar 24, 2016 at 7:14 AM Ion Gaztañaga <igaztanaga_at_[hidden]> 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.
>
> 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.
>
> Ok, your use case seems arcane, but I see how that might be useful.  Do
you want to add it as a sub-library inside Boost.Sort?