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: Ion Gaztañaga (igaztanaga_at_[hidden])
Date: 2016-03-24 11:32:30

On 24/03/2016 15:08, Phil Endecott wrote:
> 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?

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