Re: [boost] [move][sort] Asymptotically optimal stable and in-place merging and sorting with no auxiliary memory

On 24/03/2016 15:08, Phil Endecott wrote:

Ion Gazta?aga 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?

NK=1 means that the number of different keys is 1, that is, all elements are equal (NK=0 is a special number meaning NK is equal to N).

...

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.

With very few keys a rotation-based sort is used and in these cases it's very fast as most keys are already ordered and rotations are minimal. If I've correctly implemented the algorithm it should be still O(N) when merging and O(NlogN) when sorting. Best, Ion