  Dual-pivot quicksort refers to variants of classical quicksort where in the
partitioning step two pivots are used to split the input into three segments.
This can be done in different ways, giving rise to different algorithms.
Recently, a dual-pivot algorithm proposed by Yaroslavskiy received much
attention, because a variant of it replaced the well-engineered quicksort
algorithm in Sun's Java 7 runtime library. Nebel and Wild (ESA 2012) analyzed
this algorithm and showed that on average it uses 1.9n ln n + O(n) comparisons
to sort an input of size n, beating standard quicksort, which uses 2n ln n +
O(n) comparisons. We introduce a model that captures all dual-pivot algorithms,
give a unified analysis, and identify new dual-pivot algorithms that minimize
the average number of key comparisons among all possible algorithms up to a
linear term. This minimum is 1.8n ln n + O(n). For the case that the pivots are
chosen from a small sample, we include a comparison of dual-pivot quicksort and
classical quicksort. Specifically, we show that dual-pivot quicksort benefits
from a skewed choice of pivots. We experimentally evaluate our algorithms and
compare them to Yaroslavskiy's algorithm and the recently described three-pivot
quicksort algorithm of Kushagra et al. (ALENEX 2014).
