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.

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

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 25 February 2019.
HTML page formatted Wed Mar 13 12:42:45 2019.

Cite this as:
Paul E. Black, "dual-pivot quicksort", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 25 February 2019. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/dualPivotQuicksort.html