Definition: Pick two elements from the array to be sorted (the pivots), partition the remaining elements into (i) those less than the lesser pivot, (ii) those between the pivots, and (iii) those greater than the greater pivot, and recursively sort these partitions.
Generalization (I am a kind of ...)
See also quicksort.
Note: Dual-pivot quicksort is consistently faster than quicksort in practice, although classical analysis suggests that it should be slower. Sebastian Wild offers a plausible explanation why in Sebastian Wild, Why Is Dual-Pivot Quicksort Fast?, arXiv:1511.01138 v2 28 Sep 2016.
B.F. Lyon's animation showing partitioning.
Vladimir Yaroslavskiy, Dual-Pivot Quicksort algorithm, February 2009. Available at http://codeblab.com/wp-content/uploads/2009/09/DualPivotQuicksort.pdf.
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 27 November 2017.
HTML page formatted Fri Feb 23 10:06:07 2018.
Cite this as:
Paul E. Black, "dual-pivot quicksort", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 27 November 2017. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/dualPivotQuicksort.html