I don't know what happened, but I got to level 21 somehow. :)
This is cool and handy for lecturers explaining sorting/searching.
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.
On DPQS, there's apparently a method for 1.8n ln n + O(n) [3]
References:
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
2 comments
[ 8.1 ms ] story [ 244 ms ] threadThis is cool and handy for lecturers explaining sorting/searching.
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.
On DPQS, there's apparently a method for 1.8n ln n + O(n) [3]
References: