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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk