Quadsort: a stable non-recursive merge sort

Man, that's a good gif

I’ll read the article when I get the chance, but would this be in-place?

Summary: this is a non-recursive merge sort with improvements.

Benchmark of quadsort() versus C qsort():

* ~10x faster on forward-order items

* ~2x faster on reverse-order items

* ~equivalent on random-order items

Improvements:

* Ordering: when blocks of items are in order, or in reverse-order, then do special case handling, which gives quadsort O(n + log n) instead of qsort O(n * log n).

* Boundaries: compare data rather than traditional merge sort wasteful boundary checks.

Interesting, but I'm surprised if this is the first time we have sorting algorithm that is swapping more than two elements at a time. I would have guessed every possible iteration of sorting algorithms has been already explored, proven and tested.

This is still binary comparison.

There are, in general, a number of different sorting algorithms which are optimized for a specific number of elements. In this case, four. It uses five binary comparisons to sort four elements.

You can find other algorithms like this, such as an algorithm that uses seven comparisons to sort five items, or one that uses ten comparisons to sort six items.