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.
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.