NIST

dual-pivot quicksort

(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.

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

Implementation

Yaroslavskiy, Bentley, and Bloch (Java) used in JDK, Sedgewick and Wayne (Java), (C).

More information

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.


Go to the Dictionary of Algorithms and Data Structures home page.

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