(algorithm)
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 ...)
in-place sort.
Aggregate child (... is a part of or used in me.)
partition (2).
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.
Author: PEB
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 14 December 2020.
HTML page formatted Mon Dec 14 10:59:02 2020.
Cite this as:
Paul E. Black, "dual-pivot quicksort", in
Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 14 December 2020. (accessed TODAY)
Available from: https://www.nist.gov/dads/HTML/dualPivotQuicksort.html