Boost logo

Boost :

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.

Regards, Phil.

Boost list run by bdawes at, gregod at, cpdaniel at, john at