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