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: Ion Gaztañaga (igaztanaga_at_[hidden])
Date: 2016-03-24 14:49:46

On 24/03/2016 17:37, Gonzalo BG wrote:
> As a base line would also be possible to show the performance of
> `std::inplace_merge` and `std::stable_sort` when
> `std::get_temporary_buffer` returns a zero sized buffer? That is, in the
> case that no memory can be allocated, how much better are these new sorting
> algorithms compared to the std ones?

We would need to implement the algorithm ourselves as there is no way to 
stub get_temporary_buffer() to return zero unless we modify STL headers, 
which does not seem very clean ;-)

The worst case complexity of STL fallback algorithms is worse, which 
means that with big ranges the new algorithm will always win. However, 
the algorithm could have a much bigger constant factor that makes it 
inefficient for smaller ranges.

I'll try to see how STL implementations implement the fallback 
inplace_merge and maybe implement it and add it to the benchmarks.

Best,

Ion