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: 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.

Wonderful.

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.

Regards,  Phil.