Needs better in-place stable merging

[BonzaiThePenguin]

The merge operation that is currently in place needs to be redone with a more intelligent algorithm, since it has an O(n^2) worst case. Right now I'm looking at a paper called "Optimizing stable in-place merging", by Jingchao Chen, but there are many similar papers online.

[BonzaiThePenguin]

I implemented the algorithm described in "Ratio based stable in-place merging", by Pok-Son Kim and Arne Kutzner, and then I went back and wrote a much simpler version and got that working too! I should have the new version up by tomorrow night.

[Mrrl]

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 with swapping of blocks, so I could say what was the initial order of blocks by comparing of internal buffer elements.

[BonzaiThePenguin]

I'll be sure to check it out! The difference you're describing is known as the movement imitation buffer – this paper recommended using that too, but I found tagging to be faster and easier to visualize so I went with that.

I think the issue previous O(n log n) algorithms had was that they were many times slower than a standard merge sort, which made them impractical for general use. Even this one was 2-3x slower until I added a bunch of optimizations, and the Java version still has awful performance for some reason. All I've been able to determine so far is that it has something to do with the order of array accesses, and is caused by something within the JVM specifically.

[BonzaiThePenguin]

On the first run your algorithm was 20% faster than WikiSort when I removed the cache, so you've got my attention! What else is it doing differently? Structurally it looks a lot different from WikiSort, and Huang and Langston wasn't cited in Dr. Kim's and Dr. Kutzner's paper so I'm not terribly familiar with their work.

[Mrrl]

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 subblocks A and B it is before block A, and after merge it is after sorted part of (A+B). That is sequence (free, A, B) transforms to (sorted(A+B), free, rest(A or B)). Such method reduces the number of swapping operations.
As for other differences, it's difficult to say - they are well hidden in details of implementations. Now I'm not sure whether there is a good way to add cache array (of fixed size) to my implementation. Probably, yes - but it will require to duplicate half of merging functions where swap will be replaced by move.
Some description of my implementation is here: http://habrahabr.ru/post/205290/ but unfortunately it's in Russian.

[BonzaiThePenguin]

I like the idea of only pulling out the internal buffer one time at the very start and using MergeInPlace to redistribute it – I had tried doing that on my own once, but I made the mistake of always keeping the buffer at the start rather than shifting it through the array as new items are added. This caused it to become an n^3/2 operation in the worst case so I gave up and didn't think about it any further.

I'll be sure to look into the moving internal buffer idea as well. I may try bringing back the movement imitation buffer too to see if it ends up being faster with this different design.

If you're still working on GrailSort, you should try implementing the idea used in WikiSort where it scales the power-of-two math to the actual size of the array. I found that to be 10% faster overall since it reduced the number of merge operations needed when the array size isn't a power of two.

but unfortunately it's in Russian.

Not even a slight problem for Chrome! It translated it automatically and I can make sense of it.

Also, if you're interested there's now a Wikipedia article for this type of sorting algorithm. It could certainly use a Russian translation and/or more information about this class of algorithms! I only detailed the algorithm used in Kim's and Kutzner's paper and a few parts of other papers, since that's all I knew about at the time. You could also link to your GitHub project at the bottom if you're willing to release it to the Creative Commons or public domain.

[BonzaiThePenguin]

(It ended up being called "Block merge sort" because I thought Dr. Kutzner was the first to create a practical algorithm and allowed him to name it, then I decided "block sort" was a nice nickname for it.)

[Mrrl]

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 values dynamic version is 1.3 times faster than stable_sort. Not much. but I can live with it :)

[BonzaiThePenguin]

Awesome! Minor correction, though: I think it's actually .3x faster, or 30%. 1x faster means twice as fast. The test you used seems closest to RandomFew, which was only 20% faster for WikiSort.

I switched WikiSort over to extracting an internal buffer one time at the start (the code isn't uploaded yet) and it's definitely faster than what it was doing before – it went from 70% as fast to 82% as fast, without the 512-item cache. Plus the code is a lot shorter now, so that's nice. Still need to implement the other parts.

[Mrrl]

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 number of keys is slightly less than this margin (and speed of GrailSort was down to 0.75 of stable_sort's speed) and when number of keys is slightly more (and in this case speed was up to 1.3 of stable_sort's speed). I think that in "dynamic" version I could allocate array int[sqrt(N)] for blocks tagging, but it will be completely different algorithm, with O(sqrt(N)) memory (without internal buffers at all) - and it's not good to combine it with pure BlockSort.

[Mrrl]

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