I don't know what happened, but I got to level 21 somehow. :)<p>This is cool and handy for lecturers explaining sorting/searching.<p>In practice: merge, insertion and dual pivot [1] /single pivot quick(er)sort [2] are the usual tools in the toolbox, that like everything, depend on the specific use. Oh, and radix sort for rainbow tables.<p>On DPQS, there's apparently a method for 1.8n ln n + O(n) [3]<p>References:<p><pre><code> 1. http://www.iaroslavski.narod.ru/quicksort/DualPivotQuicksort.pdf
2. The FlashSort Algorithm
http://www.neubert.net/FSOIntro.html
3. Optimal Partitioning for Dual Pivot Quicksort
http://arxiv.org/abs/1303.5217
4. Algorithm 271: quickersort (1965)
http://citeseerx.ist.psu.edu/showciting?cid=846385
5. (and, of course) https://www.amazon.com/Art-Computer-Programming-Volume-Searching/dp/0201896850
(same shrtnd) http://amzn.to/134daLz</code></pre>