Subject: Re: [boost] [move][sort] Asymptotically optimal stable and in-place merging and sorting with no auxiliary memory
From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2016-03-24 10:08:52
Ion Gazta?aga <igaztanaga_at_[hidden]> wrote:
> 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.
> After reviewing several algorithms from papers and some open source
> implementations, I decided to implement one of those algorithms.
I don't think I have any practical use for it, but I still think
it's great that you've done it!
> - NK: number of keys (0 means all keys different)
Can you clarify what this means? For example, what does NK = 1 mean?
> In general, with no memory and enough keys, the algorithm needs 7,5*N
> data moves and 1,5*N comparisons. Data locality is quite high and with
> cheap-moving types the overall time can be just two-three times slower.
> With fewer keys, the algorithm might need upt to 5xN comparisons and
> 11xN moves.
What happens when the number of distinct keys is very small, e.g.
1 or 2? My recollection was that these algorithms are worse than
O(N) in that case, but I could be wrong.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk