I just tried to read this, and not only is it horrifyingly complex it isn't stable, so it doesn't really fit the bill (even if you allow for strange complexities)
Aha! Thank you. That solves a mystery for me. Skimming it a few minutes ago, I thought it claimed to be stable, and I couldn't figure out why it didn't come to mind when I thought about merge sort.
If it's not stable, then what's the point? It's not a merge sort variant by the most important measure, IMO, and as I said, I was only considering merge sort variants.
Even with all of the additional logic people have created to avoid worst case performance, quicksort is simpler than this algorithm by a huge margin.
