GrailSort - A stable, in-place, worst-case O(n*log(n)) sort

TIMESTAMPS:
0:00 - 15 numbers, random (GrailSort devolves to Insertion Sort for arrays less than 16 elements)
0:07 - 15 numbers, reverse (Insert Sort)
0:14 - 128 numbers, random
0:59 - 128 numbers, reverse
1:37 - 128 numbers, almost sorted (n - 8 elements)
1:55 - 1,024 numbers, random
2:52 - 1,024 numbers, random with stable buffer (512 elements)
3:17 - 1,024 numbers, random with dynamic buffer (less than 2 * sqrt(n) elements)
3:41 - 4,096 numbers, random
4:18 - 4,096 numbers, reverse
4:48 - 4,096 numbers, almost sorted
4:55 - 4,096 numbers, random with static buffer
5:10 - 4,096 numbers, random with dynamic buffer

This video is a visualization dedicated to a variant of Block Merge sort called GrailSort. If you're interested in learning about block merging, check it out here:

If you've heard of WikiSort before, this algorithm is pretty similar -- it comes from the same paper, after all (Check out WikiSort here, it's pretty cool as well: According to the author Andrey Astrelin, who goes by Mrrl online, its differences involve "[swapping] elements of [the] internal buffer in parallel with swapping... blocks [instead of tagging blocks]" and moving the internal buffer while merging ( The internal buffer shifting back and forth can be clearly seen in this video.

Personally, I love this sort. I think its fast performance speaks for itself, and while it may be a novelty, a stable, in-place, and logarithmic sort is hard to find. The "real" timer in the video actually underestimates GrailSort's speed, and I encourage you to check the stats in the links below.

R.I.P. Andrey Astrelin.

Find the original C version here:
Find my refactored Java version here:

sort