Andrey Astrelin

Nice algorithm :) I have wrote almost the same about 3 months ago: https://github.com/Mrrl/GrailSort . Difference is that instead of tagging blocks I've swapped elements of internal buffer in parallel...

Probably, another difference may be that in merging (both for sorting of elements in blocks and for block merging) I use moving internal buffer: before merge of two blocks or...

I've added a couple of functions in my version - sorting with fixed buffer (512 items) and with dynamic buffer (less than 2*sqrt(N) items). On 150M array with enough different...

I think that in RandomFew test number of keys is much smaller than 2*sqrt(N), so it's deep inside area of "not enough keys". I've tested algorithms in two situations: when...

Yes, pure O(sqrt(N)) memory algorithm works 40% faster than stable_sort on random data. https://github.com/Mrrl/SqrtSort

As far as I see, tagging of blocks in Huang and Langston article (by swapping of two elements) doesn't work in all situations: in some combinations of equal elements it's...

But what will you do in this example: B:[0 1 1 1] A:[1 1 1 1] B:[1 1 1 1] A:[2 2 2 2] In this case you have to...

Looks like you can work with internal buffer of any size 2*sqrt(N/k) for fixed k: - first, sort blocks of size sqrt(N*k) using buffer of sqrt(N/k) for tagging - then...

Fixed some error (with block size selection). Now in the good case (many different keys) sorting is 1.3 times faster even on 100M array.