A
Optimal Partitioning for Dual-Pivot Quicksort

arXiv:1303.5217v3 [cs.DS] 13 Oct 2015

Martin Aumüller and Martin Dietzfelbinger, Technische Universität Ilmenau

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 3-pivot quicksort algorithm of Kushagra et al. (ALENEX
2014).
Categories and Subject Descriptors: F.2.2 [Nonnumerical Algorithms and Problems]: Sorting and searching
General Terms: Algorithms
Additional Key Words and Phrases: Sorting, Quicksort, Dual-Pivot
ACM Reference Format:
Martin Aumüller and Martin Dietzfelbinger. 2014. Optimal Partitioning for Dual-Pivot Quicksort. ACM
Trans. Algor. V, N, Article A (January YYYY), 34 pages.
DOI:http://dx.doi.org/10.1145/0000000.0000000

1. INTRODUCTION

Quicksort [Hoare 1962] is a thoroughly analyzed classical sorting algorithm, described
in standard textbooks such as [Cormen et al. 2009; Knuth 1973; Sedgewick and Flajolet
1996] and with implementations in practically all algorithm libraries. Following the
divide-and-conquer paradigm, on an input consisting of n elements quicksort uses a
pivot element to partition its input elements into two parts, the elements in one part
being smaller than or equal to the pivot, the elements in the other part being larger
than or equal to the pivot, and then uses recursion to sort these parts. It is well known
that if the input consists of n elements with distinct keys in random order and the
pivot is picked by just choosing an element then on average quicksort uses 2n ln n +
A preliminary version of this work appeared in the Proceedings of the 40th International Colloquium on
Automata, Languages, and Programming (ICALP), Part 1, 33–44, 2013.
Author’s addresses: M. Aumüller; M. Dietzfelbinger, Fakultät für Informatik und Automatisierung, Technische Universität Ilmenau, 98683 Ilmenau, Germany; e-mail: {martin.aumueller,martin.dietzfelbinger}@tuilmenau.de
Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted
without fee provided that copies are not made or distributed for profit or commercial advantage and that
copies show this notice on the first page or initial screen of a display along with the full citation. Copyrights
for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted.
To copy otherwise, to republish, to post on servers, to redistribute to lists, or to use any component of this
work in other works requires prior specific permission and/or a fee. Permissions may be requested from
Publications Dept., ACM, Inc., 2 Penn Plaza, Suite 701, New York, NY 10121-0701 USA, fax +1 (212)
869-0481, or permissions@acm.org.
c YYYY ACM 1549-6325/YYYY/01-ARTA $15.00
DOI:http://dx.doi.org/10.1145/0000000.0000000
ACM Transactions on Algorithms, Vol. V, No. N, Article A, Publication date: January YYYY.

Fig. 1. Result of the partition step in dual-pivot quicksort schemes using two pivots p, q with p ≤ q. Elements
left of p are smaller than or equal to p, elements right of q are larger than or equal to q. The elements between
p and q are at least as large as p and at most as large as q.

O(n) comparisons.1 In 2009, Yaroslavskiy announced2 that he had found an improved
quicksort implementation, the claim being backed by experiments. After extensive
empirical studies, in 2009 a variant of Yaroslavskiy’s algorithm due to Yaroslavskiy,
Bentley, and Bloch became the new standard quicksort algorithm in Sun’s Java 7
runtime library. This algorithm employs two pivots to split the elements. If two pivots
p and q with p ≤ q are used, the partitioning step partitions the remaining n − 2
elements into 3 parts: elements smaller than or equal to p, elements between p and q,
and elements larger than or equal to q, see Fig. 1.3 Recursion is then applied to the
three parts. As remarked in [Wild and Nebel 2012], it came as a surprise that two pivots
should help, since in his thesis [Sedgewick 1975] Sedgewick had proposed and analyzed
a dual-pivot approach that was inferior to classical quicksort. Later, Hennequin in his
thesis [Hennequin 1991] studied the general approach of using k ≥ 1 pivot elements.
According to [Wild and Nebel 2012], he found only slight improvements that would not
compensate for the more involved partitioning procedure. (See [Wild and Nebel 2012]
for a short discussion.)
In [Wild and Nebel 2012] (see also the full version [Wild et al. 2015]), Nebel and
Wild formulated and analyzed a simplified version of Yaroslavskiy’s algorithm. (For
completeness, this algorithm is given as Algorithm 2 in Appendix B.2.) They showed that
it makes 1.9n ln n + O(n) key comparisons on average, in contrast to the 2n ln n + O(n)
of standard quicksort and the 32
15 n ln n + O(n) of Sedgewick’s dual-pivot algorithm. On
the other hand, they showed that the number of swap operations in Yaroslavskiy’s
algorithm is 0.6n ln n + O(n) on average, which is much higher than the 0.33n ln n + O(n)
swap operations in classical quicksort. In this paper we concentrate on the comparison
count as cost measure and on asymptotic results. We leave the study of other cost
measures to further investigations (which already have taken place, see [Martı́nez et al.
2015]). We consider other measures in experimental evaluations.
The authors of [Wild and Nebel 2012] state that the reason for Yaroslavskiy’s algorithm being superior were that his “partitioning method is able to take advantage
of certain asymmetries in the outcomes of key comparisons”. They also state that
“[Sedgewick’s dual-pivot method] fails to utilize them, even though being based on the
same abstract algorithmic idea”. So the abstract algorithmic idea of using two pivots
can lead to different algorithms with different behavior. In this paper we describe the
design space from which all these algorithms originate. We fully explain which simple
property makes some dual-pivot algorithms perform better and some perform worse
w.r.t. the average comparison count and identify optimal members (up to a linear term)
of this design space. The best ones use 1.8n ln n + O(n) comparisons on average—even
less than Yaroslavskiy’s method.
The first observation is that everything depends on the cost, i. e., the comparison
count, of the partitioning step. This is not new at all. Actually, in Hennequin’s thesis [Hennequin 1991] the connection between partitioning cost and overall cost for
1

In this paper ln denotes the natural logarithm and log denotes the logarithm to base 2.
archived version of the relevant discussion in a Java newsgroup can be found at
http://permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/2628. Also see [Wild and Nebel
2012].
3 In accordance with tradition, we assume in this theoretical study that all elements have different keys. Of
course, in implementations equal keys are an important issue that requires a lot of care [Sedgewick 1977].

2 An

2

quicksort variants with more than one pivot is analyzed in detail. For dual-pivot
quicksort, Hennequin proved that if the (average) partitioning cost for n elements is
a · n + O(1), for a constant a, then the average cost for sorting n elements is
6
a · n ln n + O(n).
(1)
5
The partitioning cost of some algorithms presented in this paper will have a nonconstant lower order term. Utilizing the Continuous Master Theorem of [Roura 2001],
we prove that (1) describes the average cost even if the partitioning cost is a · n + O(n1−ε )
for some ε > 0. Throughout the present paper all that interests us is the constant factor
with the leading term. (The reader should be warned that for real-life n the linear
term, which can even be negative, can have a big influence on the average number of
comparisons.)
The second observation is that the partitioning cost depends on certain details of the
partitioning procedure. This is in contrast to standard quicksort with one pivot where
partitioning always takes n − 1 comparisons. In [Wild and Nebel 2012] it is shown that
Yaroslavskiy’s partitioning procedure uses 19
12 n + O(1) comparisons on average, while
16
Sedgewick’s uses 9 n + O(1) many. The analysis of these two algorithms is based on the
study of how certain pointers move through the array, at which positions elements are
compared to the pivots, which of the two pivots is used for the first comparison, and how
swap operations exchange two elements in the array. For understanding what is going
on, however, it is helpful to forget about concrete implementations with loops in which
pointers sweep across arrays and entries are swapped, and look at partitioning with
two pivots in a more abstract way. For simplicity we shall always assume that the input
is a permutation of {1, . . . , n}. Now pivots p and q with p < q are chosen. The task is to
classify the remaining n − 2 elements into classes “small” (s = p − 1 many), “medium”
(m = q − p − 1 many), and “large” (` = n − p many), by comparing these elements one
after the other with the smaller pivot or the larger pivot, or both of them if necessary.
Note that for symmetry reasons it is inessential in which order the elements are treated.
The only choice the algorithm can make is whether to compare the current element
with the smaller pivot or the larger pivot first. Let the random variable S2 denote the
number of small elements compared with the larger pivot first, and let L2 denote the
number of large elements compared with the smaller pivot first. Then the total number
of comparisons is n − 2 + m + S2 + L2 .
Averaging over all inputs and all possible choices of the pivots the term n − 2 + m
will lead to 43 n + O(1) key comparisons on average, independently of the algorithm.
Let W = S2 + L2 , the number of elements that are compared with the “wrong” pivot
first. Then E(W ) is the only quantity that is influenced by a particular partitioning
procedure.
In the paper, we will first devise an easy method to calculate E(W ). The result of
this analysis will lead to an asymptotically optimal strategy. The basic approach is
the following. Assume a partitioning procedure is given, and assume p, q and hence
s = p − 1 and ` = n − q are fixed, and let ws,` = E(W | s, `). Denote the average number
p
q
of elements compared to the smaller [larger] pivot first by fs,`
[fs,`
]. If the elements to be
classified were chosen to be small, medium, and large independently with probabilities
s/(n − 2), m/(n − 2), and `/(n − 2), resp., then the average number of small elements
q
compared with the large pivot first would be fs,`
· s/(n − 2), similarly for the large
elements. Of course, the actual input is a sequence with exactly s [m, `] small [medium,
large] elements, and there is no independence. Still, we will show that the randomness
in the order is sufficient to guarantee that, for some ε > 0,
q
p
ws,` = fs,`
· s/n + fs,`
· `/n + O(n1−ε ).

3

(2)

p
q
The details of the partitioning procedure will determine fs,`
and fs,`
, and hence ws,` up
1−ε
to O(n ). This seemingly simple insight has two consequences, one for the analysis
and one for the design of dual-pivot algorithms:

(i) In order to analyze the average comparison count of a dual-pivot algorithm (given
p
q
by its partitioning procedure) up to a linear term, determine fs,`
and fs,`
for this
1−ε
partitioning procedure. This will give ws,` up to O(n ), which must then be averaged
over all s, ` to find the average number of comparisons in partitioning. Then apply (1).
(ii) In order to design a good partitioning procedure w.r.t. the average comparison count,
q
p
try to make fs,`
· s/n + fs,`
· `/n small.
We shall demonstrate approach (i) in Section 4. An example: As explained in [Wild
q
and Nebel 2012], if s and ` are fixed, in Yaroslavskiy’s algorithm we have fs,`
≈ ` and
p
fs,`
≈ s + m. By (2) we get ws,` = (`s + (s + m)`)/n + O(n1−ε ). This must be averaged
over all possible values of s and `. The result is 14 n + O(n1−ε ), which together with
4
19
1−ε
), close to the result from [Wild and Nebel 2012].
3 n + O(1) gives 12 n + O(n
Principle (ii) will be used to identify an asymptotically optimal partitioning procedure
that makes 1.8n ln n + O(n) key comparisons on average. In brief, such a strategy should
achieve the following: If s > `, compare (almost) all entries with the smaller pivot first
p
q
(fs,`
≈ n and fs,`
≈ 0), otherwise compare (almost) all entries with the larger pivot first
p
q
(fs,`
≈ 0 and fs,`
≈ n). Of course, some details have to be worked out: How can the
algorithm decide which case applies? In which technical sense is this strategy optimal?
We shall see in Section 5 how a sampling technique resolves these issues.
In Section 6, we will consider the following simple and intuitive strategy: If more
elements have been classified as being large instead of being small so far, compare the
next element to the larger pivot first, otherwise compare it to the smaller pivot first. We
will show that this strategy is optimal w.r.t. minimizing the average comparison count.
In implementations of quicksort, the pivot is usually chosen as the median from a
small sample of 2k + 1 elements. Intuitively, this yields more balanced subproblems,
which are smaller on average. This idea already appeared in Hoare’s original publication
[Hoare 1962] without an analysis. This was later supplied by van Emden [van Emden
1970]. The complete analysis of this variant was given by Martinez and Roura√in
[Martı́nez and Roura 2001] in 2001. They showed that the optimal sample size is n.
For this sample size the average comparison count of quicksort matches the lowerorder bound of n log n + O(n) comparisons. In practice, one usually uses a sample
of size 3. Theoretically, this decreases the average comparison count from 2n ln n +
O(n) to 1.714..n ln n + O(n). This strategy has been generalized in the obvious way to
Yaroslavskiy’s algorithm as well. The implementation of Yaroslavskiy’s algorithm in
Sun’s Java 7 uses the two tertiles in a sample of size 5 as pivots, i.e., the elements
of rank 2 and 4. In Section 7 we will analyze the comparison count of dual-pivot
quicksort algorithms with this sampling strategy. Yaroslavskiy’s algorithm has an
average comparison count of 1.704..n ln n + O(n) in this case, while the optimal average
cost is 1.623..n ln n + O(n). In that section, we will also consider a question raised by
Wild, Nebel, and Martı́nez in [Wild et al. 2014, Section 8] for Yaroslavskiy’s algorithm,
namely of which rank the pivots should be to achieve minimum sorting cost. While
using the tertiles of the input seems the obvious choice for balancing reasons, in [Wild
et al. 2014] it is shown that for Yaroslavskiy’s algorithm this minimum is attained
for ranks ≈ 0.429n and ≈ 0.698n and is ≈ 1.4931n ln n. We will show that the simple
strategy “Always compare with the larger pivot first” achieves sorting cost ≈ 1.4427n ln n,
i. e., the lower bound for comparison-based sorting, when choosing the elements of rank
n/4 and n/2 as the two pivots.
4

As noted in [Wild et al. 2013], considering only key comparisons and swap operations
does not suffice for evaluating the practicability of sorting algorithms. In Section 8, we
will present experimental results that indicate the following: When sorting integers, the
comparison-optimal algorithms of Section 5 and Section 6 are slower than Yaroslavskiy’s
algorithm. However, an implementation of the simple strategy “Always compare with
the larger pivot first” performs very well both in C++ and in Java in our experimental
setup. We will also compare our algorithms to the fast three-pivot quicksort algorithm
described in [Kushagra et al. 2014]. While comparing these algorithms, we will provide
evidence that the theoretical cost measure “cache misses” described in [Kushagra et al.
2014] nicely predicts empirical cache behavior, and comes closest for correctly predicting
running time.
We emphasize that the purpose of this paper is not to arrive at better and better
quicksort algorithms by using all kinds of variations, but rather to thoroughly analyze
the situation with two pivots, showing the potential and the limitations of this approach.
2. BASIC APPROACH TO ANALYZING DUAL-PIVOT QUICKSORT

We assume the input sequence (a1 , . . . , an ) to be a random permutation of {1, . . . , n},
each permutation occurring with probability (1/n!). If n ≤ 1, there is nothing to do;
if n = 2, sort by one comparison. Otherwise, choose the first element a1 and the last
element an as the set of pivots, and set p = min(a1 , an ) and q = max(a1 , an ). Partition
the remaining elements into elements smaller than p (“small” elements), elements
between p and q (“medium” elements), and elements larger than q (“large” elements),
see Fig. 1. Then apply the procedure recursively to these three groups. Clearly,
each

pair p, q with 1 ≤ p < q ≤ n appears as set of pivots with probability 1/ n2 . Our cost
measure is the number of key comparisons needed to sort the given input. Let Cn be the
random variable counting this number. Let Pn denote the partitioning cost to partition
the n − 2 non-pivot elements into the three groups. As explained by Wild and Nebel
[Wild and Nebel 2012, Appendix A], the average number of key comparisons obeys the
following recurrence:
n−2

E(Cn ) = E(Pn ) +

X
2
(n − k − 1) · E(Ck ).
·3
n(n − 1)

(3)

k=0

If E(Pn ) = a · n + O(1), for a constant a, this can be solved (cf. [Hennequin 1991; Wild
and Nebel 2012]) to give
E(Cn ) =

6
a · n ln n + O(n).
5

(4)

In Section 3 we will show that (4) also holds if E(Pn ) = a · n + O(n1−ε ) for some ε > 0.
For the proof we utilize the Continuous Master Theorem from [Roura 2001].
In view of this simple relation it is sufficient to study the cost of partitioning. Abstracting from moving elements around in arrays, we arrive at the following “classification
problem”: Given a random permutation (a1 , . . . , an ) of {1, . . . , n} as the input sequence
and a1 and an as the two pivots p and q, with p < q, classify each of the remaining n − 2
elements as being small, medium, or large. Note that there are exactly s := p − 1 small
elements, m := q − p − 1 medium elements, and ` := n − q large elements. Although this
classification does not yield an actual partition of the input sequence, a classification
algorithm can be turned into a partitioning algorithm using only swap operations but no
additional key comparisons. Since elements are only compared with the two pivots, the
randomness of subarrays is preserved. Thus, in the recursion we may always assume
that the input is arranged randomly.
5

We make the following observations (and fix notation) for all classification algorithms.
One key comparison is needed to decide which of the elements a1 and an is the smaller
pivot p and which is the larger pivot q. For classification, each of the remaining n − 2
elements has to be compared against p or q or both. Each medium element has to be
compared to p and q. On average, there are (n − 2)/3 medium elements. Let S2 denote
the number of small elements that are compared to the larger pivot first, i. e., the
number of small elements that need 2 comparisons for classification. Analogously, let L2
denote the number of large elements compared to the smaller pivot first. Conditioning
on the pivot choices, and hence the values of s and `, we may calculate E(Pn ) as follows:4
X
1
E(Pn ) = (n − 1) + (n − 2)/3 + n
E(S2 + L2 | s, `).
(5)
2

s+`≤n−2

We call the third summand in (5) the additional cost term (ACT), as it is the only value
that depends on the actual classification algorithm.
3. ANALYZING THE ADDITIONAL COST TERM

We will use the following formalization of a partitioning procedure: A classification
strategy is given as a three-way decision tree T with a root and n − 2 levels numbered
0, 1, . . . , n − 3 of inner nodes as well as one leaf level. The root is on level 0. Each node
v is labeled with an index i(v) ∈ {2, . . . , n − 1} and an element l(v) ∈ {p, q}. If l(v) is p,
then at node v element ai(v) is compared with the smaller pivot first; otherwise, i. e.,
l(v) = q, it is compared with the larger pivot first. The three edges out of a node are
labeled σ, µ, λ, resp., representing the outcome of the classification as small, medium,
large, respectively. The label of edge e is called c(e). On each of the 3n−2 paths each
index occurs exactly once. Each input determines exactly one path w from the root to a
leaf in the obvious way; the classification of the elements can then be read off from the
node and edge labels along this path. We call such a tree a classification tree.
Identifying a path π from the root to a leaf lf by the sequence of nodes and edges
(v1 , e1 , v2 , e2 , . . . , vn−2 , en−2 , lf) on it, we define the cost cπ as

cπ = j ∈ {1, . . . , n − 2} | l(vj ) = q ∧ c(ej ) = σ or l(vj ) = p ∧ c(ej ) = λ .
For a given input, the cost of the path associated with this input exactly describes the
number of additional comparisons on this input. An example for such a classification
tree is given in Figure 2.
We let S2T [LT2 ] denote the random variable that for a random input counts the number
of small [large] elements classified in nodes with label q [p]. We now describe how we
can calculate the ACT of a classification tree T . First consider fixed s and ` and let
the input excepting the pivots be arranged randomly. For a node v in T , we let sv , mv ,
and `v , resp., denote the number of edges labeled σ, µ, and λ, resp., from the root to
v. By the randomness of the input, the probability that the element classified at v is
“small”, i. e., that the edge labeled σ is used, is exactly (s − sv )/(n − 2 − level(v)). The
probability that it is “medium” is (m − mv )/(n − 2 − level(v)), and that it is “large” is
(` − `v )/(n − 2 − level(v)). The probability pvs,` that node v in the tree is reached is then
just the product of all these edge probabilities on the unique path from the root to v.
The probability that the edge labeled σ out of a node v is used can then be calculated as
pvs,` · (s − sv )/(n − 2 − level(v)). Similarly, the probability that the edge labeled λ is used
is pvs,` · (` − `v )/(n − 2 − level(v)). Note that all this is independent of the actual ordering
4 We

use the following notation throughout this paper: To indicate that sums run over all
P
(s, `) with s, ` ≥ 0 and s + ` ≤ n − 2 we simply write s+`≤n−2 .

6

n
2

combinations

3:p
µ

σ
2:q
σ

4:p

µ

4:p
σ

λ

4:q

4:p

2:q

σ
a2 : σ
a3 : σ
a4 : σ

λ

µ

σ

λ

2:p
σ

...

µ

2:p

2:p

4:q

λ

λ

4:p

λ

a2 : σ
a3 : µ
a4 : µ

a2 : µ
a3 : µ
a4 : µ

a2 : λ
a3 : µ
a4 : µ

c2 : 0

c3 : 0

c4 : 1

c1 : 1

4:p

µ

...

a2 : λ
a3 : λ
a4 : λ
c5 : 3

Fig. 2. An example for a decision tree to classify three elements a2 , a3 , and a4 according to the pivots a1 and
a5 . Five out of the 27 leaves are explicitly drawn, showing the classification of the elements and the costs ci
of the specific paths.

in which the classification tree inspects the elements. We can thus always assume some
fixed ordering and forget about the label i(v) of node v.
By linearity of expectation, we can sum up the contribution to the additional comparison count for each node separately. Thus, we may calculate
E(S2T +LT2 | s, `) =

X
v∈T
l(v)=q

pvs,` ·

X
s − sv
` − `v
+
pvs,` ·
.
n − 2 − level(v)
n − 2 − level(v)

(6)

v∈T
l(v)=p

The setup developed so far makes it possible to describe the connection between a
classification tree T and its average comparison count in general. Let FpT and FqT be
two random variables that denote the number of elements that are compared with the
q
smaller and larger pivot first, respectively, when using T . Then let fs,`
= E FqT | s, `

p
resp. fs,`
= E FpT | s, ` denote the average number of comparisons with the larger resp.
smaller pivot first, given s and `. Now, if it was decided in each step by independent
random experiments with the correct expectations s/(n − 2), m/(n − 2), and `/(n − 2),
resp., whether an element is small, medium, or large, it would be clear that for example
q
fs,`
· s/(n − 2) is the average number of small elements that are compared with the
larger pivot first. The next lemma shows that one can indeed use this intuition in the
calculation of the average comparison count, except that one gets an additional O(n1−ε )
term due to the elements tested not being independent.
L EMMA 3.1. Let T be a classification tree. Let E(PnT ) be the average number of key
comparisons for classifying an input of n elements using T . Then there exists a constant
ε > 0 such that

X  q

4
1
p
E(PnT ) = n + n
fs,` · s + fs,`
· ` + O n1−ε .
3
2 · (n − 2) s+`≤n−2
7

P ROOF. Fix p and q (and thus s, m, and `). We will show that

E(S2T + LT2 | s, `) =

q
p
fs,`
· s + fs,`
·`

n−2


+ O n1−ε .

(7)

(The lemma then follows by substituting this into (5).)
We call a node v in T on-track (to the expected values) if

s
1
s − sv
≤ 1/12
−
n − 2 n − level(v) − 2
n
`
1
` − `v
l(v) = p and
≤ 1/12 .
−
n − 2 n − level(v) − 2
n
l(v) = q and

or
(8)

Otherwise we call v off-track.
We first obtain an upper bound. Starting from (6), we calculate:

E(S2T + LT2 | s, `) =

X

pvs,` ·

v∈T,l(v)=q

s − sv
+
n − 2 − level(v)

X

pvs,` ·

v∈T,l(v)=p

` − `v
n − 2 − level(v)

X
s
`
=
pvs,` ·
+
pvs,` ·
+
n−2
n−2
v∈T,l(v)=q
v∈T,l(v)=p


X
s
s − sv
v
ps,`
−
+
n − 2 − level(v) n − 2
v∈T,l(v)=q


X
`
` − `v
v
ps,`
−
n − 2 − level(v) n − 2
X

v∈T,l(v)=p

≤

X

pvs,` ·

v∈T,l(v)=q

X
v∈T,l(v)=q
v on-track

s
+
n−2

pvs,`
n1/12

+

X

pvs,` ·

v∈T,l(v)=p

X
v∈T,l(v)=q
v off-track

pvs,` +

`
+
n−2
X

v∈T,l(v)=p
v on-track

pvs,`
n1/12

+

X

pvs,` ,

v∈T,l(v)=p
v off-track

(9)

where the last step follows by separating on-track and off-track nodes and using (8).
(For off-track nodes we use that the left-hand side of the inequalities in (8) is at most
1.) For the sums in the last line of (9), consider each level of the classification tree
separately. Since the probabilities pvs,` for nodes v on the same level sum up to 1, the
q
contribution of the 1/n1/12 terms is bounded by O(n11/12 ). Using the definition of fs,`
p
and fs,` , we continue as follows:
8

X

E(S2T +LT2 | s, `) ≤

pvs,` ·

v∈T,l(v)=q

=

=

s
+
n−2

q
p
fs,`
· s + fs,`
·`

n−2
q
fs,`

·s+

p
fs,`

n−2
n−3
X

X

X
`
+
n−2



pvs,` + O n11/12

v∈T
v off-track

v∈T,l(v)=p



pvs,` + O n11/12

X

+

pvs,` ·

v∈T,v off-track

·`

+



Pr(the node reached on level k is off-track) + O n11/12 , (10)

k=0

where in the last step we just rewrote the sum to consider each level in the classification
tree separately. So, to show (7) it remains to bound the sum in (10) by O(n1−ε ).
To do this, consider a random input that is classified using T . Using an appropriate
tail bound, viz. the method of average bounded differences, we will show that with very
high probability we do not reach an off-track node in the classification tree in the first
n − n3/4 levels. Intuitively, this means that it is highly improbable that underway the
observed fraction of small elements deviates very far from the average s/(n − 2).
Let Xj be the 0-1 random variable that is 1 if the j-th classified element is small;
let Yj be the 0-1 random variable that is 1 if the j-th classified element is large. Let
si = X1 + · · · + Xi and `i = Y1 + · · · + Yi for 1 ≤ i ≤ n − 2.
C LAIM 3.2. Let 1 ≤ i ≤ n − 2. Then
Pr(|si − E(si )| > n2/3 ) ≤ 2 exp(−n1/3 /2), and
Pr(|`i − E(`i )| > n2/3 ) ≤ 2 exp(−n1/3 /2).
P ROOF. We prove the first inequality. First, we bound the difference cj between
the expectation of si conditioned on X1 , . . . , Xj resp. X1 , . . . , Xj−1 for 1 ≤ j ≤ i. Using
linearity of expectation we may calculate
cj = E(si | X1 , . . . , Xj ) − E(si | X1 , . . . , Xj−1 )
=

j
X

i
X

Xk +

k=1

k=j+1
i
X

j−1

i

k=1

k=j

X
X s − sj−1
s − sj
−
Xk −
n−j−2
n−j−1
i
X

s − sj−1
n−j−1
k=j
k=j+1


i−j
i−j
i−j+1
= Xj − Xj ·
+ (s − sj−1 )
−
n−j−2
n−j−2 n−j−1




i−j
n−i−2
= Xj 1 −
− (s − sj−1 )
n−j−2
(n − j − 1)(n − j − 2)




i−j
s − sj−1
≤ max Xj 1 −
,
≤ 1.
n−j−2
n−j−1
= Xj +

s − sj−1 − Xj
−
n−j−2

9

In this situation we may apply the bound known as the method of averaged bounded
differences (see [Dubhashi and Panconesi 2009, Theorem 5.3]), which reads
!
t2
,
Pr(|si − E(si )| > t) ≤ 2 exp − P
2 j≤i c2j
and get
Pr(|si − E(si )| > n2/3 ) ≤ 2 exp



−n4/3
2i


,

which is not larger than 2 exp(−n1/3 /2).
Assume that |si − E(si )| = |si − i · s/(n − 2)| ≤ n2/3 . We have
s
n2/3
s
n2/3
s − si
s(1 − i/(n − 2))
≤
+
=
−
−
.
n−2 n−2−i
n−2
n−2−i
n−2−i
n−2−i
That means that for each of the first i ≤ n − n3/4 levels with very high probability we
are in an on-track node on level i, because the deviation from the ideal case that we
see a small element with probability s/(n − 2) is n2/3 /(n − 2 − i) ≤ n2/3 /n3/4 = 1/n1/12 .
Thus, for the first n − n3/4 levels the contribution of the sums of the probabilities of
off-track nodes in (10) is at most n11/12 . For the last n3/4 levels of the tree, we use that
the contribution of the probabilities that we reach an off-track node on level i is at most
1 for a fixed level.
11/12
This shows that the contribution of the sum
). This finishes the
 in (10) is O(n
T
T
proof of the upper bound on E S2 + L2 | s, ` given in (10). The calculations for the
lower bound are similar and are omitted here.
There is the following technical complication when using this lemma in analyzing
a strategy that is turned into a dual-pivot quicksort algorithm: The cost bound is
a · n + O(n1−ε ), and Hennequin’s result (Equation (4)) cannot be applied directly to such
partitioning costs. However, the next theorem says that the leading term of (4) applies
to this situation as well, and the additional O(n1−ε ) term in the partitioning cost is
completely covered in the O(n) error term of (4).
T HEOREM 3.3. Let A be a dual-pivot quicksort algorithm that gives rise to a classification tree Tn for each subarray of length n. Assume E(PnTn ) = a · n + O(n1−ε ) for all n,
for some constants a and ε > 0. Then E CnA = 65 an ln n + O(n).
P ROOF. By linearity of expectation we may split the partitioning cost into two terms
t1 (n) = a · n and t2 (n) = K · n1−ε , solve recursion (3) independently for these two cost
terms, and add the results. Applying (4) for average partitioning cost t1 (n) yields an
average comparison count of 65 an ln n + O(n). Obtaining the bound of O(n) for the term
t2 (n) is a standard application of the Continuous Master Theorem of Roura [Roura
2001], and has been derived for the dual-pivot quicksort recurrence by Wild, Nebel, and
Martı́nez in a recent technical report [Wild et al. 2014, Appendix D]. For completeness,
the calculation is given in Appendix A.
Lemma 3.1 and Theorem 3.3 tell us that for the analysis of the average comparison
p
q
count of a dual-pivot quicksort algorithm we just have to find out what fs,`
and fs,`
are
for this algorithm. Moreover, to design a good algorithm (w.r.t. the average comparison
q
p
count), we should try to make fs,`
· s + fs,`
· ` small for each pair s, `.
10

4. ANALYSIS OF SOME KNOWN CLASSIFICATION STRATEGIES

In this section, we will study different classification strategies in the light of the
formulas from Section 3.
Oblivious Strategies. We will first consider strategies that do not use information of
previous classifications for future classifications. To this end, we call a classification
tree oblivious if for each level all nodes v on this level share the same label l(v) ∈ {p, q}.
This means that these algorithms do not react to the outcome of previous classifications,
but use a fixed sequence of pivot choices. Examples for such strategies are, e. g.,
— always compare to the smaller pivot first,
— always compare to the larger pivot first,
— alternate the pivots in each step.
Let fnq denote the average number of comparisons to the larger pivot first. By assumption
q
this value is independent of s and `. Hence these strategies make sure that fs,`
= fnq
p
and fs,` = n − 2 − fnq for all pairs of values s, `.
Applying Lemma 3.1 gives us
X
1
·
(f q · s + (n − 2 − fnq ) · `) + O(n1−ε )
· (n − 2) s+`≤n−2 n




q
X
X
n
−
2
−
f
4
fnq
n
s + n
` + O(n1−ε )
= n + n
·
·
3
·
(n
−
2)
2 · (n − 2)
2
s+`≤n−2
s+`≤n−2


X
4
1
5
= n + n · 
s + O(n1−ε ) = n + O(n1−ε ).
3
3
2

E(Pn ) =

4
n+
3

n
2



s+`≤n−2

Using Theorem 3.3 we get E(Cn ) = 2n ln n + O(n)—the leading term being the same
as in standard quicksort. So, for each strategy that does not adapt to the outcome
of previous classifications, there is no difference to the average comparison count of
classical quicksort. Note that this also holds for randomized strategies such as “flip a
coin to choose the pivot used in the first comparison”, since such a strategy can be seen
as a probability distribution on oblivious strategies.
Yaroslavskiy’s Algorithm. Following [Wild and Nebel 2012, Section 3.2], Yaroslavskiy’s
algorithm is an implementation of the following strategy Y: Compare ` elements to q
q
p
first, and compare the other elements to p first. We get that fs,`
= ` and fs,`
= s + m.
Applying Lemma 3.1, we get

X  s`
4
1
(s + m)`
E(PnY ) = n + n
+
+ O(n1−ε ).
3
n
−
2
n
−
2
2
s+`≤n−2

Of course, it is possible to evaluate this sum by hand. We used Maple R to obtain
1−ε
E(PnY ) = 19
). Using Theorem 3.3 gives E(Cn ) = 1.9n ln n + O(n), as in [Wild
12 n + O(n
and Nebel 2012].
Sedgewick’s Algorithm. Following [Wild and Nebel 2012, Section 3.2], Sedgewick’s
algorithm amounts to an implementation of the following strategy S: Compare (on
average) a fraction of s/(s + `) of the keys with q first, and compare the other keys with p
q
p
first. We get fs,`
= (n − 2) · s/(s + `) and fs,`
= (n − 2) · `/(s + `).
11

Plugging these values into Lemma 3.1, we calculate

X  s2
4
1
`2
16
S
E(Pn ) = n + n
+
+ O(n1−ε ) =
n + O(n1−ε ).
3
s
+
`
s
+
`
9
2
s+`≤n−2

Applying Theorem 3.3 gives E(Cn ) = 2.133... · n ln n + O(n), as known from [Wild and
Nebel 2012].
Obviously, this is worse than the oblivious strategies considered before.5 This is easily
explained intuitively: If the fraction of small elements is large, it will compare many
elements with q first. But this costs two comparisons for each small element. Conversely,
if the fraction of large elements is large, it will compare many elements to p first, which
is again the wrong decision.
Since Sedgewick’s strategy seems to do exactly the opposite of what one should do to
lower the comparison count, we consider the following modified strategy S 0 : For given p
and q, compare (on average) a fraction of s/(s + `) of the keys with p first, and compare
the other keys with q first. (S 0 simply uses p first when S would use q first and vice
versa.)
1−ε
Using the same analysis as above, we get E(Pn ) = 14
), which yields
9 n + O(n
E(Cn ) = 1.866... · n ln n + O(n)—improving on the standard algorithm and even on
Yaroslavskiy’s algorithm! Note that this has been observed by Wild in his Master’s
Thesis as well [Wild 2013].
Remark. Swapping the first comparison with p and q as in the strategy described
above is a general technique. In fact, if the leading coefficient of the average number of
comparisons for a fixed rule for choosing p or q first is α, e. g., α = 2.133... for strategy
S, then the leading coefficient of the strategy that does the opposite is 4 − α, e. g.,
4 − 2.133... = 1.866... as in strategy S 0 .
5. AN ASYMPTOTICALLY OPTIMAL CLASSIFICATION STRATEGY

Looking at the previous sections, all strategies used the idea that we should compare a
certain fraction of elements to p first, and the other elements to q first. In this section, we
will study the following strategy I: If s > ` then always compare with p first, otherwise
always compare with q first.
Of course, for an implementation of this strategy we have to deal with the problem
of finding out which case applies before the comparisons have been made. We shall
analyze a guessing strategy to resolve this.
5.1. Analysis of the Idealized Classification Strategy

Assume for a moment that for a given random input with pivots p, q the strategy
“magically” knows whether s > ` or not and correctly determines the pivot that should
be used for all comparisons. For fixed s and ` this means that for s > ` the classification
strategy makes exactly ` additional comparisons, and for s ≤ ` it makes s additional
comparisons.
When we start from (5), a standard calculation shows that for this strategy
X
4
1
3
E(Pn ) = n + n
min(s, `) = n + O(1).
(11)
3
2
2
s+`≤n−2

Applying (4), we get E(Cn ) = 1.8n ln n + O(n), which is by 0.1n ln n smaller than the
average number of key comparisons in Yaroslavskiy’s algorithm.
5 We

remark that in his thesis Sedgewick [Sedgewick 1975] focused on the average number of swaps, not on
the comparison count.

12

To see that this method is asymptotically optimal, recall that according to Lemma 3.1
q
the average comparison count is determined up to a linear term by the parameters fs,`
p
q
q
and fs,`
= n − 2 − fs,`
. Strategy I chooses these values such that fs,`
is either 0 or n − 2,
minimizing each term of the sum in Lemma 3.1—and thus minimizing the sum.

5.2. Guessing Whether s < ` or not

We explain how the idealized classification strategy just described can be approximated
by an implementation. The idea is to make a few comparisons and use the outcome as a
basis for a guess.
After p and q are chosen, classify the first ns = O(n1−ε ) many elements (the sample)
and calculate s0 and `0 , the number of small and large elements in the sample. If s0 < `0 ,
compare the remaining n − 2 − ns elements with q first, otherwise compare them with p
first. We say that the guess was correct if s0 < `0 and s < ` or s0 ≥ `0 and s ≥ `. In order
not to clutter up formulas, we will always assume that n1−ε is an integer. One would
otherwise work with dn1−ε e.
We incorporate guessing errors and sampling cost into (11) as follows:
1
4
E(Pn ) = n + n
3
2

X



Pr (guess correct | s, `) · min(s, `) +

Pr(guess wrong | s, `) · max(s, `) + O(n1−ε )
n/2 n−s 
2 X X
4
= n + n
Pr(guess correct | s, `) · s +
3

2 s=0 `=s+1
Pr(guess wrong | s, `) · ` + O(n1−ε ),
s+`≤n−2

(12)

where the cost for comparing the elements in the sample is covered by the O(n1−ε ) term.
The following lemma says that for a wide range of values s and ` the probability of a
guessing error is exponentially small.
L EMMA 5.1. Let s and ` with s ≤ ` − n3/4 and ` ≥ n3/4 for n ∈ N be given. Let
ns = n2/3 . Then Pr(guess wrong | s, `) ≤ exp −n1/6 /18 .
P ROOF. Let Xi be a random variable that is −1 if the i-th P
classified element of the
ns
sample is large, 0 if it is medium, and 1 if it is small. Let d = i=1
Xi .
As in the proof of Lemma 3.1, we want to apply the method of averaged bounded
differences. Using the assumptions on the values of s and `, straightforward calculations
show that E(d) ≤ −ns /n1/4 = −n5/12 . Furthermore, we have that
ci = E(d | X1 , . . . , Xi ) − E(d | X1 , . . . , Xi−1 ) ≤ 3, for 1 ≤ i ≤ ns .
To see this, we let si and `i denote the number of small and large elements, respectively,
that are still present after the first i elements have been classified, i. e., X1 , . . . , Xi have
been determined. Let Yi be the 0-1 random variable that is 1 if and only if Xi is 1, and
13

let Zi be the 0-1 random variable that is 1 if and only if Xi is −1. We calculate:
|E(d | X1 , . . . , Xi ) − E(d | Xi , . . . , Xi−1 )|

ns 
i
X
X
=
Xj +
Pr(Xj = 1 | X1 , . . . , Xi ) − Pr(Xj = −1 | X1 , . . . , Xi )
j=1

−

j=i+1

i−1
X
j=1

Xj −

ns 
X


Pr(Xj = 1 | X1 , . . . , Xi−1 ) − Pr(Xj = −1 | X1 , . . . , Xi−1 )

j=i

 X

ns 
ns 
X
si
`i
si−1
`i−1
= Xi +
−
−
−
n−i n−i
n−i+1 n−i+1
j=i+1
j=i




si−1 − Yi
`i−1 − Zi
si−1
`i−1
= Xi + (ns − i) ·
−
− (ns − i + 1) ·
−
n−i
n−i
n−i+1 n−i+1




(ns − i) · (Zi − Yi )
ns − i ns − i + 1
ns − i + 1 ns − i
= Xi +
+ si−1
−
+ `i−1
−
n−i
n−i
n−i+1
n−i+1 n−i
= Xi +

(ns − i) · (Zi − Yi )
n − ns
+ (`i−1 − si−1 ) ·
n−i
(n − i)(n − i + 1)

≤ |Xi | + |Zi − Yi | +

`i−1 − si−1
≤ 3.
n−i+1

The method of averaged bounded differences (see [Dubhashi and Panconesi 2009,
Theorem 5.3]) now implies that
!
t2
, for t > 0,
Pr(d > E(d) + t) ≤ exp − P
2 i≤ns c2i
which with t = n5/12 ≤ −E(d) yields
 1/6 
n
Pr(d > 0) ≤ exp −
.
18
Of course, we get an analogous result for s ≥ n3/4 and ` ≤ s − n3/4 .
Classification strategy SP works as follows: Classify the first ns = n2/3 elements. Let
0 0
s [` ] be the number of elements classified as being small [large]. If s0 > `0 then use p
for the first comparison for the remaining elements, otherwise use q.
We can now analyze the average number of key comparisons of this strategy turned
into a dual-pivot quicksort algorithm.
T HEOREM 5.2. The average comparison count of strategy SP turned into a dual-pivot
quicksort algorithm is 1.8n ln n + O(n).
P ROOF. We only have to analyze the expected classification cost. First, we classify
ns many elements. The number of key comparisons for these classifications is at most
2n2/3 = O(n1−ε ). By symmetry, we may focus on the case that s ≤ `. We distinguish the
following three cases:
14

(1) ` ≤ n3/4 : The contribution of terms in (12) satisfying this case is at most
3/4

n
`
2 XX

` = O(n1/4 ).
n
2

`=0 s=0

3/4

(2) ` − n
≤ s ≤ `: Let m1 (s, n) = min(s + n3/4 , n − s). The contribution of terms in (12)
satisfying this case is at most
n/2 m1 (s,n)

3/4

2 X

n

X

2

`=s

s=0

` = O(n3/4 ).

3/4

(3) ` ≥ n
and s ≤ ` − n . Let m2 (`, n) = min(n − `, ` − n3/4 ). Following Lemma 5.1,
the probability of guessing wrong is at most exp(−n1/6 /18). The contribution of this
case in (12) is hence at most



m2 (`,n) 
m2 (`,n)
n
n
X
X
X
X
2
n
2

s + exp(−n1/6 /18)` =  n
s + o(1) = + O(1).
n
6
2
2
3/4
3/4
s=0
s=0
`=n

`=n

Using these contributions in (12), we expect a partitioning step to make 32 n + O(n1−ε )
key comparisons. Applying Theorem 3.3, we get E(Cn ) = 1.8n ln n + O(n).
In this section we have seen an asymptotically optimal strategy. In the next section we
will present the optimal classification strategy. Unfortunately, it is even more unrealistic
than the idealized strategy I from above. However, we will give an implementation that
comes very close to the optimal strategy in terms of the number of comparisons.
6. THE OPTIMAL CLASSIFICATION STRATEGY AND ITS IMPLEMENTATION

We will consider two more strategies, an optimal (but not algorithmic) strategy, and an
algorithmic strategy that is optimal up to a very small error term.
We first study the (unrealistic!) setting where s and `, i. e., the number of small
resp. large elements, are known to the algorithm after the pivots are chosen, and the
classification tree can have different node labels for each such pair of values. Recall
that sv and `v , resp., denote the number of elements that have been classified as small
and large, resp., when at node v in the classification tree. We consider the following
strategy O: Given s and `, the comparison at node v is with the smaller pivot first if
s − sv > ` − `v , otherwise it is with the larger pivot first.6
T HEOREM 6.1. Strategy O is optimal, i. e., its ACT is at most as large as ACTT for
all classification trees T . When using O in a dual-pivot quicksort algorithm, we have
E(CnO ) = 1.8n ln n + O(n).
P ROOF. The proof of the first statement (optimality) is surprisingly simple. Fix the
two pivots, and consider equation (6). For each node v in the classification tree Strategy
O chooses the label that minimizes the contribution of this node to (6). So, it minimizes
each term of the sum, and thus minimizes the additional cost term in (5).
We now prove the second statement. For this, we first derive an upper bound of
1.8n ln n + O(n) for the average number of comparisons, and then show that this is tight.
For the first part, let an input with n entries and two pivots be given, so that there
are s small and ` large elements. Assume s ≥ `. Omit all medium elements to obtain a
reduced input (a1 , . . . , an0 ) with n0 = s + `. For 0 ≤ i ≤ n0 let si and `i denote the number
of small resp. large elements remaining in (ai+1 , . . . , an0 ). Let Di = si − `i . Of course we
6 This

strategy was suggested to us by Thomas Hotz (personal communication).

15

have D0 = s − ` and Dn0 = 0. Let i1 < i2 < · · · < ik be the list of indices i with Di = 0.
(In particular, ik = n0 .) Rounds i with Di = 0 are called zero-crossings. Consider some j
with Dij = Dij+1 = 0. The numbers Dij +1 , . . . , Dij+1 −1 are nonzero and have the same
positive [or negative] sign. The algorithm compares aij +2 , . . . , aij+1 with the smaller
[larger] pivot first, and aij +1 with the larger pivot first. Since {aij +1 , . . . , aij+1 } contains
the same number of small and large elements, the contribution
 of this segment to the
additional comparison count is 12 (ij+1 − ij ) − 1 or 12 (ij+1 − ij ) .
If D0 > 0, i. e., s > `, all elements in {a1 , . . . , ai1 } are compared with the smaller
pivot first, and this set contains 12 (i1 − (s − `)) large elements (and 12 (i1 + (s − `)) small
elements), giving a contribution of 12 (i1 − (s − `)) to the additional comparison count.
Overall, the additional comparison count S2 + L2 (see the end of Section 2, in particular
(5)) of strategy O on the considered input is
k−1

n0 − (s − `)
i1 − (s − `) X ij+1 − ij
+
− k∗ =
− k∗ = ` − k∗ ,
2
2
2
j=1

(13)

for some correction term k ∗ ∈ {0, . . . , k − 1}.
Averaging the upper bound ` over all pivot choices, we obtain the following bound for
the additional cost term of strategy O:


X
X
1 

E (S2 + L2 ) ≤ n · 2 ·
`+
` .
(14)
2

s+`≤n
`<s

`≤n/2

This gives an average number of at most 1.5n+O(1) comparisons. For such a partitioning
cost we can use (4) and obtain an average comparison count for sorting via strategy O
of at most 1.8n ln n + O(n).
It remains to show that this is tight. We shall see that the essential step in this
analysis is to show that the average (over all inputs) of the number of zero-crossings
(the number k from above, excepting the zero-crossing at position n) is O(log n). Again,
we temporarily omit medium elements to simplify calculations, i. e., we assume that the
number of small and large elements together is n0 . Fix a position n0 − 2i, for 1 ≤ i ≤ n0 /2.
If Dn0 −2i = 0, then there are as many small elements as there are large elements in
the last 2i positions of the input. Consequently, the input has to contain between i and
n0 − i small elements, otherwise no zero-crossing is possible. The probability that a
random input (excepting the two pivots) of n0 elements has exactly s small elements is
1/(n0 + 1), for 0 ≤ s ≤ n0 . Let Zn0 be the random variable that denotes the number of
zero-crossings for an input of n0 elements excepting the two pivots. We calculate:
E(Zn0 ) =

X

Pr(there is a zero-crossing at position n0 − 2i)

1≤i≤n0 /2
0

0

n /2 n −i
1 XX
Pr(Dn0 −2i = 0 | s small elements)
= 0
n + 1 i=1 s=i


n0 /2 n0 −i 2i
n0 /2 n0 /2 2i
n0 −2i
n0 −2i
1 X X i · s−i
2 X X i · s−i
= 0
≤ 0
,


n0
n0
n + 1 i=1 s=i
n + 1 i=1 s=i
s
s

where the last step follows by symmetry: replace s > n0 /2 by n0 − s.
16

√

By using the well-known estimate 2ii = Θ(22i / i) (which follows directly from
Stirling’s approximation), we continue by

E(Zn0 ) = Θ

=Θ

=Θ

1
n0
1
n0
1
n0

0
 nX
/2

i=1
0
 nX
/2

i=1
0
 nX
/2

i=1

0

n /2
22i X
√
i s=i

n0 −2i
s−i

n0
s



0

n /2
22i X (n0 − s) · . . . · (n0 − s − i + 1) · s · . . . · (s − i + 1)
√
n0 · . . . · (n0 − 2i + 1)
i s=i
0

n /2−i i−1
X Y (n0 + 2j − 2k)(n0 − 2j − 2k)
n0 + 1
√
,
(n0 − 2k + 1)(n0 − 2k)
i(n0 −2i+1) j=0 k=0

(15)

where the last step follows by an index transformation using j = n0 /2−s and multiplying
22i into the terms of the rightmost fraction. We now obtain an upper bound for the
rightmost product:

i−1
Y
k=0

i−1
Y
(n0 + 2j − 2k)(n0 − 2j − 2k)
≤
(n0 − 2k + 1)(n0 − 2k)


1−

k=0

2j
n0 − 2k

2 !


≤

1−

2j
n0

2 !i
.

We substitute this bound into (15). Bounding the rightmost sum of (15) by an integral,
and using Maple R , we obtain

E(Zn0 ) = O

=O

1
n0
1
n0

0
 nX
/2

0

√

i=1



n +1
i(n0 − 2i + 1)

n0 /2

E(Zn0 ) = O 

X
i=1

n0 /2


1−

0

2t
n0



2 !i

dt + 1



Γ(i + 1)
n0 + 1
0
√
· n ·
+1 ,
Γ(i + 3/2)
i(n0 − 2i + 1)
1≤i≤n0 /2
X

involving the Gamma function Γ(x) =
we may continue by calculating



Z


R∞
0

√
tx−1 e−t dt. Since Γ(i+1)/Γ(i+3/2) = Θ(1/ i),


 0
n /4
X1
n0 + 1
 = O
+
i(n0 − 2i + 1)
i
i=1

n0 /2

X
i=n0 /4+1


1
 = O(log n0 ).
n0 − 2i + 1

Now we generalize the analysis to the case that the input contains medium elements.
Let (a1 , . . . , an ) be a random input. Omit all medium elements to obtain a reduced
input (a1 , . . . , an0 ) with n0 = s + `. The additional cost term of strategy O on the reduced
input is the same as on the original input, since medium elements influence neither
the decisions of the strategy on elements of the reduced input nor the additional cost
term. Starting from (13), we may bound the difference between the additional cost term
E(S2 + L2 ) and the bound given in (14) by the average over all s, ` of the values k ∗ . This
17

O
σ

λ

σ

µ

C
σ

λ

σ

σ

σ

λ

σ

µ

σ

λ

−→
Next element

Next element

σ

σ
←−

Fig. 3. Visualization of the decision process when inspecting an element using strategy O (left) and C (right).
Applying strategy O from left to right uses that of the remaining elements three are small and one is large,
so it decides that the element should be compared with p first. Applying strategy C from right to left uses
that of the inspected elements two were small and only one was large, so it decides to compare the element
with p first, too. Note that the strategies would differ if, e. g., the rightmost element were a medium element.

is bounded by the average over all s, ` of the values Zn0 , hence by


X
X
X
1
1 


`+
` − E(S2 + L2 ) ≤ n
E(Zs+` | s, `)
n 2
2

s+`≤n
`<s

2

`≤n/2

=

1

n
2

s+`≤n−2

X

O(log(s + `)) = O(log n).

s+`≤n−2

Since O(log n) is in O(n1−ε ), the influence of these O(log n) terms to the total average
sorting cost is bounded by O(n), see Theorem 3.3 and Appendix A.
While making an algorithm with minimum ACT possible, the assumption that the exact
number of small and large elements is known is of course not true for a real algorithm
or for a fixed tree. We can, however, identify a real, algorithmic partitioning strategy
whose ACT differs from the optimal one only by a logarithmic term. We study the
following strategy C: The comparison at node v is with the smaller pivot first if sv > lv ,
otherwise it is with the larger pivot first.
While O looks into the future (“Are there more small elements or more large elements
left?”), strategy C looks into the past (“Have I seen more small or more large elements
so far?”). It is not hard to see that for some inputs the number of additional comparisons
of strategy O and C can differ significantly. The next theorem shows that averaged over
all possible inputs, however, there is only a small difference.
T HEOREM 6.2. Let ACTO resp. ACTC be the ACT for classifying n elements using
strategy O resp. C. Then ACTC = ACTO +O(log n). When using C in a dual-pivot quicksort
algorithm, we get E(CnC ) = 1.8n ln n + O(n).
P ROOF. Assume that strategy O inspects the elements in the order an−1 , . . . , a2 ,
while C uses the order a2 , . . . , an−1 . If the strategies compare the element ai to different
pivots, then there are exactly as many small elements as there are large elements in
{a2 , . . . , ai−1 } or {a2 , . . . , ai }, depending on whether i is even or odd, see Figure 3.
The same calculation as the proof of the previous theorem shows that ACTC − ACTO
is O(log n), which—as mentioned in the proof of the previous theorem—sums up to
a total additive contribution of O(n) when using strategy C in a dual-pivot quicksort
algorithm.
Thus, dual-pivot quicksort with strategy C has average cost at most O(n) larger than
dual-pivot quicksort using the (unrealistic) optimal strategy O.
We have identified two asymptotically optimal strategies (SP and C) which can be
used in an actual algorithm. Note that both strategies have an additional summand of
18

O(n). Unfortunately, the solution of the dual-pivot quicksort recurrence, cf. Theorem 3.3,
does not give any information about the constant hidden in the O(n) term. However, the
average partitioning cost of strategy C differs by only O(log n) from the partitioning cost
of the optimal strategy O, while SP differs by O(n1−ε ). So one may be led to believe that
C has a (noticeably) lower average comparison count for real-world input lengths. In
Section 8 we will see that differences are clearly visible in the average comparison count
measured in experiments. However, we will also see that the necessity for bookkeeping
renders implementations of strategy C impractical.
7. CHOOSING PIVOTS FROM A SAMPLE

In this section, we consider the variation of quicksort where the pivots are chosen
from a small sample. Intuitively, this guarantees better pivots in the sense that the
partition sizes are more balanced. For classical quicksort, the Median-of-k strategy is
optimal w.r.t. minimizing the average comparison count [Martı́nez and Roura 2001],
which means that the median in a sample of k elements is chosen as the pivot. The
standard implementation of Yaroslavskiy’s algorithm in Sun’s Java 7 uses an intuitive
generalization of this strategy: it chooses the two tertiles in a sample of five elements
as pivots.7
We will compare dual-pivot quicksort algorithms which use the two tertiles of the
first five elements of the input as the two pivots with classical quicksort. Moreover, we
will see that the optimal pivot choices for dual-pivot quicksort are not the two tertiles of
a sample, but rather the elements of rank k/4 and k/2.
We remark that Wild, Nebel, and Martı́nez [Wild et al. 2014] provide a much more
detailed study of pivot sampling in Yaroslavskiy’s algorithm.
7.1. Choosing the Two Tertiles in a Sample of Size 5 as Pivots

We sort the first five elements and take the second and fourth elements aspivots. The
probability that p and q, p < q, are chosen as pivots is exactly (s · m · `)/ n5 . Following
Hennequin [Hennequin 1991, pp. 52–53], for average partitioning cost E(Pn ) = a · n +
O(1) we get
E(Cn ) =

20
1
· a · n ln n + O(n) =
· a · n ln n + O(n),
H6 − H2
19

(16)

where Hn denotes the n-th harmonic number.
When applying Lemma 3.1, we have average partitioning cost a · n + O(n1−ε ). Using
the same argument as in the proof of Theorem 3.3, the average comparison count
becomes 20/19 · a · n ln n + O(n) in this case. (This a special case of the much more
general pivot sampling strategy that is described and analyzed in [Wild et al. 2014,
Theorem 6.2].)
We will now investigate the effect on the average number of key comparisons in
Yaroslavskiy’s algorithm and the asymptotically optimal strategy SP from Section 5.
The average number of medium elements remains (n−2)/3. For strategy Y, we calculate
(again using Maple R )
X ` · (2s + m) · s · m · `
4
1
34
+ O(n1−ε ) =
n + O(n1−ε ).
E(PnY ) = n + n
3
n
−
5
21
5
s+`≤n−5

Applying (16), we get E(CnY ) = 1.704..n ln n + O(n) key comparisons on average. (Note
that [Wild et al. 2013] calculated this leading coefficient as well.) This is slightly better
than “clever quicksort”, which uses the median of a sample of three elements as a single
7

In an ordered set S = {x1 , . . . , xk }, the two tertiles are the elements of rank dk/3e and d2k/3e.

19

pivot element and achieves 1.714..n ln n + O(n) key comparisons on average [van Emden
1970]. For strategy SP, we get (similarly as in Section 5)
X
37
2
4
s · s · m · ` + O(n1−ε ) =
n + O(n1−ε ).
E(PnSP ) = n + n
3
24
5
s+`≤n−5
s≤`

Again using (16), we obtain E(CnSP ) = 1.623..n ln n + O(n), improving further on the
leading coefficient compared to clever quicksort and Yaroslavskiy’s algorithm.
7.2. Pivot Sampling in Classical Quicksort and Dual-Pivot Quicksort

In the previous subsection, we have shown that optimal dual-pivot quicksort using a
sample of size 5 clearly beats clever quicksort which uses the median of three elements.
We will now investigate how these two variants compare when the sample size grows.
The following proposition, which is a special case of [Hennequin 1991, Proposition
III.9 and Proposition III.10], will help in this discussion.
P ROPOSITION 7.1. Let a · n + O(1) be the average partitioning cost of a quicksort
algorithm A that chooses the pivot(s) from a sample of size k, for constants a and k. Then
the following holds:
(1) If k + 1 is even and A is a classical quicksort variant that chooses the median of
these k samples, then the average sorting cost is
1
· a · n ln n + O(n).
Hk+1 − H(k+1)/2
(2) If k + 1 is divisible by 3 and A is a dual-pivot quicksort variant that chooses the two
tertiles of these k samples as pivots, then the average sorting cost is
1
· a · n ln n + O(n).
Hk+1 − H(k+1)/3
Note that for classical quicksort we have partitioning cost n − 1. Thus, the average
1
sorting cost becomes Hk+1 −H
n ln n + O(n).
(k+1)/2
For dual-pivot partitioning algorithms, the probability that p and q, p < q, are chosen
as pivots in a sample of size k where k + 1 is divisible by 3 is exactly
 q−p−1  n−q 
p−1
(k−2)/3

(k−2)/3

n
k

(k−2)/3

.

SP
Thus, the average partitioning cost E(Pn,k
) of strategy SP using a sample of size k can
be calculated as follows:




4
2 X
s
m
`
SP
E(Pn,k ) = n + n
· s + O(n1−ε ).
(17)
3
(k
−
2)/3
(k
−
2)/3
(k
−
2)/3
k
s≤`

SP
Unfortunately, we could not find a closed form of E(Pn,k
). Some calculated values in
which classical and dual-pivot quicksort with strategy SP use the same sample size can
be found in Table I. These values clearly indicate that starting from a sample of size 5
classical quicksort has a smaller average comparison count than dual-pivot quicksort.8
This raises the question whether dual-pivot quicksort is inferior to classical quicksort
using the Median-of-k strategy.
8 Note

that this statement does not include that these two variants have different linear terms for the same
sample size.

20

Table I. Comparison of the leading term of the average cost of classical quicksort
and dual-pivot quicksort for specific sample sizes. Note that for real-world input sizes,
however, the linear term can make a big difference.
Sample Size
Median (QS)
Tertiles (DP QS)

5
1.622..n ln n
1.623..n ln n

11
1.531..n ln n
1.545..n ln n

17
1.501..n ln n
1.523..n ln n

41
1.468..n ln n
1.504..n ln n

7.3. Optimal Segment Sizes for Dual-Pivot Quicksort

It is known from, e.g., [Martı́nez and Roura 2001] that for classical quicksort in which
the pivot is chosen as the median of a fixed-sized sample, the leading term of the
average comparison count converges with increasing sample size to the lower bound
of (1/ ln 2) · n ln n = 1.4426..n ln n. Wild, Nebel, and Martı́nez observed in [Wild et al.
2014] that this is not the case for Yaroslavskiy’s algorithm, which makes at least
1.4931..n ln n − O(n) comparisons on average no matter how well the pivots are chosen.
In this section, we will show how to match the lower bound for comparison-based sorting
algorithms with a dual-pivot approach.
We study the following setting, which was considered in [Martı́nez and Roura 2001;
Wild et al. 2014] as well. We assume that for a random input of n elements9 we can
choose (for free) two pivots w.r.t. a vector ~τ = (τ1 , τ2 , τ3 ) such that the input contains
exactly τ1 n small elements, τ2 n medium elements, and τ3 n large elements. Furthermore,
we consider the (simple) classification strategy L: “Always compare with the larger pivot
first.”
The following lemma says that this strategy achieves the minimum possible average
comparison count for comparison-based sorting algorithms, 1.4426..n ln n, when setting
τ = ( 41 , 14 , 12 ).
P
L EMMA 7.2. Let ~τ = (τ1 , τ2 , τ3 ) with 0 < τi < 1 and i τi = 1, for i ∈ {1, 2, 3}. Assume
that for each input size n we can choose two pivots such that there are exactly τ1 · n small,
τ2 · n medium, and τ3 · n large elements. Then the comparison count of strategy L is10
p~τ (n) ∼

1 + τ + τ2
P 1
n ln n.
− 1≤i≤3 τi ln τi

This value is minimized for ~τ ∗ = (1/4, 1/4, 1/2) giving


∗
1
n ln n = 1.4426..n ln n.
p~τ (n) ∼
ln 2
P ROOF. On an input consisting of n elements, strategy L makes n + (τ1 + τ2 )n
comparisons. Thus, the comparison count of strategy L follows the recurrence
p~τ (n) = n + (τ1 + τ2 )n + p~τ (τ1 · n) + p~τ (τ2 · n) + p~τ (τ3 · n).
Using the Discrete Master Theorem from [Roura 2001, Theorem 2.3, Case (2.1)], we
obtain the following solution for this recurrence:
p~τ (n) ∼

1 + τ1 + τ2
n ln n.
P3
i=1 τi ln τi

−

∗

Using Maple R , one finds that p~τ is minimized for ~τ ∗ = ( 14 , 14 , 12 ), giving p~τ (n) ∼
1.4426..n ln n.
9 We

disregard the two pivots in the following discussion.
f (n) ∼ g(n) means that limn→∞ f (n)/g(n) = 1.

10 Here,

21

Table II. Overview of the algorithms considered in the experiments.
Abbreviation
QS
Y
L
S
SP
C
K

Full Name
Classical Quicksort
Yaroslavskiy’s Algorithm
Larger Pivot First
Sedgewick’s Algorithm (modified)
Sample Algorithm
Counting Algorithm
3-Pivot-Algorithm

Strategy
—
Section 4
Section 4
Section 4
Section 5
Section 6
—

Pseudocode
e.g., [Wild and Nebel 2012, Algo. 1]
Algorithm 2 (Page 29)
Algorithm 3 (Page 29)
Algorithm 5 (Page 31)
Algorithm 6 (Page 32)
Algorithm 7 (Page 32)
[Kushagra et al. 2014, Algo. A.1.1]

The reason why strategy L with this particular choice of pivots achieves the lower
bound is simple: it makes (almost) the same comparisons as does classical quicksort
using the median of the input as pivot. On an input of length n, strategy L makes 3/2n
key comparisons and then makes three recursive calls to inputs of length n/4, n/4, n/2.
On an input of length n, classical quicksort using the median of the input as the pivot
makes n comparisons to split the input into two subarrays of length n/2. Now consider
only the recursive call on the left subarray. After n/2 comparisons, the input is split into
two subarrays of size n/4 each. Now there remain two recursive calls on two subarrays
of size n/4, and one recursive call on a subarray of size n/2 (the right subarray of the
original input), like in strategy L. Since classical quicksort using the median of the
input clearly makes n log n key comparisons, this bound must also hold for strategy L.
8. EXPERIMENTS

We have implemented the methods presented in this paper in C++ and Java. Our
experiments were carried out on an Intel i7-2600 at 3.4 GHz with 16 GB RAM running
Ubuntu 13.10 with kernel version 3.11.0. For compiling C++ code, we used gcc in version
4.8. For compiling Java code, we used Oracle’s Java 8 SDK. All Java runtime tests were
preceeded by a warmup phase for the just-in-time compiler (JIT), in which we let each
algorithm sort 10 000 inputs of length 100 000.
For better orientation, the algorithms considered in this section are presented in
Table II. Pseudocode for the dual-pivot methods is provided in Appendix B. In the
following, we use a calligraphic letter both for the classification strategy and the actual
dual-pivot quicksort algorithm.
In Section 8.1, we experimentally evaluate the average comparison count of the
algorithms considered here. In Section 8.2, we focus on the actual running time needed
to sort a given input. The charts of our experiments can be found at the end of this
paper.
8.1. The Average Comparison Count

We first have a look at the number of comparisons needed to sort a random input of up
to 229 integers. We did not switch to a different sorting algorithm, e. g., insertion sort, to
sort short subarrays.
Figure 5 shows the results of our experiments for algorithms that choose the pivots
directly from the input. We see that for practical values of n the lower order terms in
the average comparison count have a big influence on the number of comparisons for
all algorithms. (E.g., for Yaroslavskiy’s algorithm this lower order term is dominated by
the linear term −2.46n, as known from [Wild and Nebel 2012].) Nevertheless, we may
conclude that the theoretical studies on the average comparison count correspond to
what can be observed in practice. Note that there is a difference between the optimal
strategies SP and C. We also see that the modified version of Sedgewick’s algorithm
beats Yaroslavskiy’s algorithm, as calculated in Section 4.
Figure 6 shows the same experiment for algorithms that choose the pivots from
a small sample. For dual-pivot quicksort variants, we used two different versions.
22

Algorithms Y, SP, C, L choose the tertiles of a sample of size 5 as pivots. QS is classical
quicksort using the median of three strategy. Y 0 is Yaroslavskiy’s algorithm with the
tertiles of a sample of size 11 as the pivots; L0 is algorithm L using the third- and sixthlargest element in a sample of size 11 as the pivots. This plot confirms the theoretical
results from Section 7. Especially, the simple strategy L beats Yaroslavskiy’s algorithm
for a sample of size 11 for the pivot choices introduced in Section 7.3.
8.2. Running Times

We now consider the running times of the algorithms for sorting a given input. We
restrict our experiments to sorting random permutations of the integers {1, . . . , n}. It
remains future work to compare the algorithms in more detail.
As a basis for comparison with other methods, we also include the three pivot quicksort algorithm described in [Kushagra et al. 2014] (about 8% faster than Yaroslavskiy’s
algorithm in their setup), which we call K. Similarly to classical quicksort, this algorithm uses two pointers to scan the input from left-to-right and right-to-left until these
pointers cross. Classifications are done in a symmetrical way: First compare to the
middle pivot; then (appropriately) compare either to the largest or smallest pivot. (In
this way, each element is compared to exactly two pivots.) Elements are moved to a
suitable position by the help of two auxiliary pointers. We note that the pseudocode
from [Kushagra et al. 2014, Algorithm A.1.1] uses multiple swaps when fewer assignments are sufficient to move elements. We show pseudocode of our implementation in
Appendix C.
In our experiments, subarrays of size at most 16, 20, and 23 were sorted by insertion
sort for classical quicksort, dual-pivot quicksort, and the three pivot quicksort algorithm,
respectively. Furthermore, strategy SP uses strategy L to sort inputs that contain no
more than 1024 elements.
C++ Experiments. We first discuss our results on C++ code compiled with gcc-4.8.
Since the used compiler flags might influence the observed running times, we considered
4 different compiler settings. In setting 1 we have compiled the source code with -O2, in
setting 2 with -O2 -funroll-loops, in setting 3 with -O3, and in setting 4 with -O3 -funrollloops. The option -funroll-loops tells the compiler to unroll (the first few iterations of)
a loop. In all settings, we used -march=native, which means that the compiler tries to
optimize for the specific CPU architecture we use during compilation.
The experiments showed that there is no significant difference between the settings
using -O2 and those using -O3. So, we just focus on the first two compiler settings
which use -O2. The running time results we obtained in these two settings are shown
in Figure 7 and Figure 8 at the end of this paper. We first note that loop unrolling
makes all algorithms behave slightly worse with respect to running times. Since a
single innocuous-looking compiler flag may have such an impact on running time, we
stress that our results do not allow final statements about the running time behavior of
quicksort variants. In the following, we restrict our evaluation to setting 1.
With respect to average running time, we get the following results, see Figure 7
(the discussion uses the measurements obtained for inputs of size 227 ): Yaroslavskiy’s
algorithm is the fastest algorithm, but the difference to the dual-pivot algorithm L
and the three pivot algorithm K is negligible. The asymptotically comparison-optimal
sampling algorithm SP cannot compete with these three algorithms w.r.t. running time.
On average it is about 7.2% slower than algorithm Y. Classical quicksort is about 8.3%
slower than Y. The slowest algorithm is the counting algorithm C, on average it is about
14.8% slower than Y.
Now we consider the significance of running time differences. For that, we let each
algorithm sort the same 1 000 inputs containing 227 items. In Table III we consider the
23

number of cases which support the hypothesis that an algorithm is a given percentage
faster than another algorithm. The table shows that the difference in running time is
about 1% smaller than the average suggested if we consider only significant running
time differences, i. e., differences that were observed in at least 95% of the inputs. We
conclude that there is no significant difference between the running times of the three
fastest quicksort variants.
Table III. Comparison of the actual running times of the algorithms on 1000 different inputs of size 227 . A table cell
in row labelled “A” and column labelled “B” contains a string “x%/y%/z%” and is read as follows: “In about 95%,
50%, and 5% of the cases algorithm A was more than x, y, and z percent faster than algorithm B, respectively.”
Y
L
K
SP
QS

Y
—
–/–/0.8%
—
—
—

L
–/–/0.9%
—
–/–/0.3%
—
—

K
–/1.0%/2.1%
–/0.9%/2.1%
—
—
—

SP
6.4%/7.2%/8.0%
5.8%/7.0%/8.5%
4.7%/6.0%/7.6%
—
—

QS
7.2%/8.3%/9.4%
7.0%/8.1%/9.5%
5.9%/7.2%/8.5%
–/1.0%/2.4%
—

C
13.9%/14.8%/15.8%
13.7%/14.6%/15.8%
12.3%/13.6%/14.9%
5.8%/7.1%/8.4%
4.7%/5.9%/7.2%

The good performance of the simple strategy “always compare to the larger pivot
first” is especially interesting, because it is bad from a theoretical point of view: it
makes 2n ln n comparisons and 0.6n ln n swaps on average. So, it does not improve in
both of these cost measures compared to classical quicksort, but is still faster. We may
try to explain these differences in measured running times by looking at the average
instruction count and the cache behavior of these algorithms. (The latter is motivated
by the cost measure “cache misses” considered in [Kushagra et al. 2014].) Table IV
shows measurements of the average total instruction count and the average number of
L1/L2 cache misses,11 both in total and in relation to algorithm K.
With respect to the average number of total instructions, we see that strategy K
needs the fewest instructions on average. It is about 1.2% better than algorithm L.
Furthermore, it is 7.1% better than the sampling algorithm SP, about 11% better than
Yaroslavskiy’s algorithm and about 12.7% better than classical quicksort. As expected,
the theoretically optimal strategy C needs by far the most instructions because of its
necessity for bookkeeping. However, focusing exclusively on the total instruction count
does not predict the observed running time behavior accurately. (In particular, Y should
be slower than classical quicksort, which has also been observed in [Wild et al. 2013]
with respect to Sun’s Java 7.)
The authors of [Kushagra et al. 2014] conjectured that another cost measure—the
average number of cache misses—explains observed running time behavior. From Table IV we see that strategy K shows the best performance with respect to cache misses,
confirming the theoretical results of [Kushagra et al. 2014]. In our experiments, we
observed that the relative difference of L1 cache misses between the 1-, 2-, and 3-pivot
algorithms match the theoretical results from [Kushagra et al. 2014]. (According to
their calculations, dual-pivot variants should incur about 16% more cache misses, while
classical quicksort should incur about 44% more cache misses.) This might explain why
classical quicksort is the slowest algorithm, but cannot explain why the dual-pivot
algorithms Y and L can compete with the three pivot algorithm.
With respect to L2 cache misses, we see that the cache misses are much higher
than predicted. Compared to the 3-pivot algorithm, classical quicksort incurs 178%
more cache misses, and the worst dual-pivot algorithm w.r.t. L2 misses has 49% more
cache misses. Since L2 misses have a much higher impact on the CPU cycles spent
waiting for memory, this might amplify differences between these algorithms. In general,
11 Such

statistics can be collected, e.g., by using the performance application programming interface from
http://icl.cs.utk.edu/papi/.

24

Table IV. Average number of total instructions and cache misses scaled by n ln n for the
algorithms considered in this section. In parentheses, these figures are set into relation to
the values measured for algorithm K. (The relative difference has been calculated directly
from the experimental data.) The figures were obtained by sorting 1 000 inputs of length 227
separately by each algorithm using the compiler flag -O2.
Algorithm
QS
Y
SP
C
L
K

total #instructions
10.58n ln n (+12.7%)
10.42n ln n (+11.0%)
10.05n ln n (+ 7.1%)
14.08n ln n (+50.1%)
9.50n ln n (+ 1.2%)
9.38n ln n ( — )

L1 misses
0.142n ln n (+47.9%)
0.111n ln n (+15.6%)
0.111n ln n (+15.6%)
0.111n ln n (+15.6%)
0.111n ln n (+15.6%)
0.096n ln n ( — )

L2 misses
0.030n ln n (+178.1%)
0.015n ln n (+ 39.9%)
0.014n ln n (+ 31.7%)
0.012n ln n (+ 11.8%)
0.016n ln n (+ 49.0%)
0.011n ln n (
— )

we note that only a fraction of about 1% of the instructions lead to cache misses.
Consequently, one has to accurately measure the cycles spent waiting for memory
in these situations. Investigating these issues is a possible direction for future work.
With respect to other cost measures, Martı́nez, Nebel, and Wild [Martı́nez et al. 2015]
analyzed branch misses in classical quicksort and Yaroslavskiy’s algorithm. Their result
is that the difference in the average number of branch mispredictions between these
two algorithms is too small to explain differences in empirical running time. Based
on our experimental measurements, we believe that this cost measure cannot explain
running time differences between dual-pivot quicksort algorithms, either.
We conclude that in the light of our experiments neither the average number of
instructions nor the average number of cache misses can fully explain empirical running
time.
Java Experiments. Figure 9 shows the running time measurements we got using
Oracle’s Java 8. Again, there is no significant difference between algorithms K, L, and
Y. The three pivot quicksort algorithm K is the fastest algorithm using Java 8 on our
setup. It is about 1.3% faster than Yaroslavskiy’s algorithm on average. The optimal
strategy C is about 37% slower on average than algorithm K. Classical quicksort and
the sampling strategy SP are about 7.7% slower on average.
9. CONCLUSION AND OPEN QUESTIONS

We have studied dual-pivot quicksort algorithms in a unified way and found optimal
partitioning methods that minimize the average number of key comparisons up to O(n).
This minimum is 1.8n ln n + O(n). We showed an optimal pivot choice for a simple dualpivot quicksort algorithm and conducted an experimental study of the practicability of
dual-pivot quicksort algorithms.
Several open questions remain. From a theoretical point of view, one should generalize
our algorithms to the case that three or more pivots are used. At the moment, the
optimal average comparison count for k-pivot quicksort is unknown for k ≥ 3. This is
the subject of ongoing work. From both a theoretical and an engineering point of view,
the most important question is to find a cost measure that accurately predicts empirical
running time behavior of variants of quicksort algorithms. Here we could only provide
evidence that neither standard measures like the average comparison count or the
average swap count, nor empirical measures like the average instruction count or the
cache behavior predict running time correctly when considered in isolation.
Acknowledgements. The authors thank Thomas Hotz for a useful suggestion regarding the optimal strategy of Section 6, and Pascal Klaue for implementing the algorithms
and carrying out initial experiments. The first author thanks Timo Bingmann, Michael
Rink, and Sebastian Wild for interesting and useful discussions. We thank the referees
of the conference and journal submissions for their insightful comments, which helped
a lot in improving the presentation. We especially thank the referee who pointed out a
25

way of showing that the lower order term of most algorithms considered in this paper is
O(n), not only o(n ln n).
REFERENCES
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to
Algorithms (3rd ed.). MIT Press.
Devdatt P. Dubhashi and Alessandro Panconesi. 2009. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press.
Pascal Hennequin. 1991. Analyse en moyenne d’algorithmes: tri rapide et arbres de recherche. Ph.D. Dissertation. Ecole Politechnique, Palaiseau. http://www-lor.int-evry.fr/∼pascal/
C. A. R. Hoare. 1962. Quicksort. Comput. J. 5, 1 (1962), 10–15.
Donald E. Knuth. 1973. The Art of Computer Programming, Volume III: Sorting and Searching. AddisonWesley.
Shrinu Kushagra, Alejandro López-Ortiz, Aurick Qiao, and J. Ian Munro. 2014. Multi-Pivot Quicksort: Theory
and Experiments. In Proc. of the 16th Meeting on Algorithms Engineering and Experiments (ALENEX’14).
SIAM, 47–60.
Conrado Martı́nez, Markus E. Nebel, and Sebastian Wild. 2015. Analysis of Branch Misses in Quicksort. In
Proc. of the 12th Meeting on Analytic Algorithmics and Combinatorics (ANALCO’ 15). 114–128.
Conrado Martı́nez and Salvador Roura. 2001. Optimal sampling strategies in quicksort and quickselect.
SIAM J. Comput. 31, 3 (2001), 683–705.
Salvador Roura. 2001. Improved master theorems for divide-and-conquer recurrences. J. ACM 48, 2 (2001),
170–205.
Robert Sedgewick. 1975. Quicksort. Ph.D. Dissertation. Standford University.
Robert Sedgewick. 1977. Quicksort with equal keys. SIAM J. Comput. 6, 2 (1977), 240–268.
Robert Sedgewick and Philippe Flajolet. 1996. An Introduction to the Analysis of Algorithms. Addison-WesleyLongman.
M. H. van Emden. 1970. Increasing the efficiency of quicksort. Commun. ACM 13, 9 (1970), 563–567.
Sebastian Wild. 2013. Java 7’s Dual Pivot Quicksort. Master’s thesis. University of Kaiserslautern.
Sebastian Wild and Markus E. Nebel. 2012. Average case analysis of Java 7’s dual pivot quicksort. In Proc. of
the 20th European Symposium on Algorithms (ESA’12). 825–836.
Sebastian Wild, Markus E. Nebel, and Conrado Martı́nez. 2014. Analysis of Pivot Sampling in Dual-Pivot
Quicksort. CoRR abs/1412.0193 (2014).
Sebastian Wild, Markus E. Nebel, and Ralph Neininger. 2015. Average Case and Distributional Analysis of
Dual-Pivot Quicksort. ACM Transactions on Algorithms 11, 3 (2015), 22.
Sebastian Wild, Markus E. Nebel, Raphael Reitzig, and Ulrich Laube. 2013. Engineering Java 7’s Dual Pivot
Quicksort Using MaLiJAn. In Proc. of the 15th Meeting on Algorithms Engineering and Experiments
(ALENEX’13). 55–69.

A. MISSING DETAILS OF THE PROOF OF THEOREM ??

Here we solve recurrence (3) for partitioning cost E(Pn ) at most K · n1−ε . We use the
Continuous Master Theorem of Roura [Roura 2001], whose statement we will review
first.
T HEOREM A.1 ([R OURA 2001, T HEOREM 18]). Let Fn be recursively defined by
(
bn ,
for 0 ≤ n < N,
Pn−1
Fn =
tn + j=0 wn,j Fj , for n ≥ N,
where the toll function tn satisfies tn ∼ Knα logβ (n) as n → ∞ for constants K 6= 0, α ≥
0, β > −1. Assume there exists a function w : [0, 1] → R such that
Z (j+1)/n
n−1
X
wn,j −
w(z) dz = O(n−d ),
(18)
j/n

j=0

for a constant d > 0. Let H := 1 −

R1
0

z α w(z) dz. Then we have the following cases:
26

(1) If H > 0, then Fn ∼ tn /H.
(2) If H = 0, then Fn ∼ (tn ln n)/Ĥ, where
1

Z

z α ln(z)w(z) dz.

Ĥ := −(β + 1)
0

(3) If H < 0, then Fn ∼ Θ(nc ) for the unique c ∈ R with
Z 1
z c w(z) dz = 1.
0

We now solve recurrence (3) for tn = K · n1−ε , for some ε > 0. First, observe that
recurrence (3) has weights
wn,j =

6(n − j − 1)
.
n(n − 1)

We define the shape function w(z) as suggested in [Roura 2001] by
w(z) = lim n · wn,zn = 6(1 − z).
n→∞

Now we have to check (18) to see whether the shape function is suitable. We calculate:
Z (j+1)/n
n−1
X
wn,j −
w(z) dz
j/n

j=0

=6

n−1
X
j=0

=6

n−1
X
j=0

<6

n−1
X
j=0

n−j−1
−
n(n − 1)

Z

(j+1)/n

(1 − z) dz
j/n

n − j − 1 2j + 1
1
+
−
n(n − 1)
2n2
n
1
= O(1/n).
2n(n − 1)

Thus, w is a suitable shape function. By observing that
Z 1
H := 1 − 6
z 1−ε (1 − z) dz < 0,
0

we conclude that the third case of Theorem A.1 applies for our recurrence. Consequently,
we have to find the unique c ∈ R such that
Z 1
6
z c (1 − z) dz = 1,
0

which is true for c = 1. Thus, an average partitioning cost of at most K · n1−ε yields
average sorting cost of O(n).
B. DUAL-PIVOT QUICKSORT: ALGORITHMS IN DETAIL
B.1. General Setup

The general outline of a dual-pivot quicksort algorithm is presented as Algorithm 1.
To get an actual algorithm we have to implement a partition function that partitions
the input as depicted in Figure 1. A partition procedure in this paper has two output
27

Algorithm 1 Dual-Pivot-Quicksort (outline)
procedure Dual-Pivot-Quicksort(A, left, right)
1 if right − left ≤ THRESHOLD then
2
InsertionSort(A, left, right);
3
return ;
4 if A[right] > A[left] then
5
swap A[left] and A[right];
6 p ← A[left];
7 q ← A[right];
8 partition(A, p, q, left, right, posp , posq );
9 Dual-Pivot-Quicksort(A, left, posp - 1);
10 Dual-Pivot-Quicksort(A, posp + 1, posq - 1);
11 Dual-Pivot-Quicksort(A, posq + 1, right);
variables posp and posq that are used to return the positions of the two pivots in the
partitioned array.
For moving elements around, we make use of the following two operations.

procedure rotate3(a, b, c)
1 tmp ← a;
2 a ← b;
3 b ← c;
4 c ← tmp;

procedure rotate4(a, b, c, d)
1 tmp ← a;
2 a ← b;
3 b ← c;
4 c ← d;
5 d ← tmp;

B.2. Yaroslavskiy’s Partitioning Method

As mentioned in Section 4, Yaroslavskiy’s algorithm makes sure that for ` large elements
in the input ` or ` − 1 elements will be compared to the larger pivot first. How does it
accomplish this? By default, it compares to the smaller pivot first, but for each large
elements that it sees, it will compare the next element to the larger pivot first.
Algorithm 2 shows the partition step of (a slightly modified version of) Yaroslavskiy’s
algorithm. In contrast to the algorithm studied in [Wild and Nebel 2012], it saves
an index check at Line 8, and uses a rotate3 operation to save assignments. (In our
experiments this makes Yaroslavskiy’s algorithm about 4% faster.)
B.3. Algorithm Using “Always Compare to the Larger Pivot First”

Algorithm 3 presents an implementation of strategy L (“Always compare to the larger
pivot first”). Like Yaroslavskiy’s algorithm, it uses three pointers into the array. One
pointer is used to scan the array from left to right until a large element has been
found (moving small elements to a correct position using the second pointer on the
way). Subsequently, it scans the array from right to left using the third pointer until a
non-large element has been found. These two elements are then placed into a correct
position. This is repeated until the two pointers have crossed. The design goal is to check
as rarely as possible if these two pointers have met, since this event occurs infrequently.
(In contrast, Yaroslavskiy’s algorithm checks this for each element scanned by index k
in Algorithm 2.)
This strategy makes 2n ln n comparisons and 1.6n ln n assignments on average.
28

Algorithm 2 Yaroslavskiy’s Partitioning Method
procedure Y-Partition(A, p, q, left, right, posp , posq )
1 l ← left + 1; g ← right − 1; k ← l;
2 while k ≤ g do
3
if A[k] < p then
4
swap A[k] and A[l];
5
l ← l + 1;
6
else
7
if A[k] > q then
8
while A[g] > q do
9
g ← g − 1;
10
if k < g then
11
if A[g] < p then
12
rotate3(A[g], A[k], A[l]);
13
l ← l + 1;
14
else
15
swap A[k] and A[g];
16
g ← g − 1;
17
k ← k + 1;
18 swap A[left] and A[l − 1];
19 swap A[right] and A[g + 1];
20 posp ← l − 1; posq ← g + 1;

Algorithm 3 Always Compare To Larger Pivot First Partitioning
procedure L-Partition(A, p, q, left, right, posp , posq )
1 i ← left + 1; k ← right − 1; j ← i;
2 while j ≤ k do
3
while q < A[k] do
4
k ← k − 1;
5
while A[j] < q do
6
if A[j] < p then
7
swap A[i] and A[j];
8
i ← i + 1;
9
j ← j + 1;
10
if j < k then
11
if A[k] > p then
12
rotate3(A[k], A[j], A[i]);
13
i ← i + 1;
14
else
15
swap A[j] and A[k];
16
k ← k − 1;
17
j ← j + 1;
18 swap A[left] and A[i − 1];
19 swap A[right] and A[k + 1];
20 posp ← i − 1; posq ← k + 1;

29

Fig. 4. An intermediate partitioning step in Sedgewick’s algorithm.

B.4. Partitioning Methods Based on Sedgewick’s Algorithm

Algorithm 4 shows Sedgewick’s partitioning method as studied in [Sedgewick 1975].
Sedgewick’s partitioning method uses two pointers i and j to scan through the input.
It does not swap entries in the strict sense, but rather has two “holes” at positions i1
resp. j1 that can be filled with small resp. large elements. “Moving a hole” is not a
swap operation in the strict sense (three elements are involved), but requires the same
amount of work as a swap operation (in which we have to save the content of a variable
into a temporary variable [Sedgewick 1975]). An intermediate step in the partitioning
algorithm is depicted in Figure 4.
The algorithm works as follows: Using i it scans the input from left to right until it
has found a large element, always comparing to the larger pivot first. Small elements
found in this way are moved to a correct final position using the hole at array position
i1 . Subsequently, using j it scans the input from right to left until it has found a small
element, always comparing to the smaller pivot first. Large elements found in this
way are moved to a correct final position using the hole at array position j1 . Now it
exchanges the two elements at positions i resp. j and continues until i and j have met.
Algorithm 4 Sedgewick’s Partitioning Method
procedure S-Partition(A, p, q, left, right, posp , posq )
1 i ← i1 ← left; j ← j1 := right;
2 while true do
3
i ← i + 1;
4
while A[i] ≤ q do
5
if i ≥ j then
6
break outer while
7
if A[i] < p then
8
A[i1 ] ← A[i]; i1 ← i1 + 1; A[i] ← A[i1 ];
9
i ← i + 1;
10
j ← j − 1;
11
while A[j] ≥ p do
12
if A[j] > q then
13
A[j1 ] ← A[j]; j1 ← j1 − 1; A[j] ← A[j1 ];
14
if i ≥ j then
15
break outer while
16
j ← j − 1;
17
A[i1 ] ← A[j]; A[j1 ] ← A[i];
18
i1 ← i1 + 1; j1 ← j1 − 1;
19
A[i] ← A[i1 ]; A[j] ← A[j1 ];
20 A[i1 ] ← p; A[j1 ] ← q;
21 posp ← i1 ; posq ← j1 ;
Algorithm 5 shows an implementation of the modified partitioning strategy from
Section 4. In the same way as Algorithm 4 it scans the input from left to right until it
has found a large element. However, it uses the smaller pivot for the first comparison in
30

this part. Subsequently, it scans the input from right to left until it has found a small
element. Here, it uses the larger pivot for the first comparison.

Algorithm 5 Sedgewick’s Partitioning Method, modified
procedure S2-Partition(A, p, q, left, right, posp , posq )
1 i ← i1 ← left; j ← j1 := right;
2 while true do
3
i ← i + 1;
4
while true do
5
if i ≥ j then
6
break outer while
7
if A[i] < p then
8
A[i1 ] ← A[i]; i1 ← i1 + 1; A[i] ← A[i1 ];
9
else if A[i] > q then
10
break inner while
11
i ← i + 1;
12
j ← j − 1;
13
while true do
14
if A[j] > q then
15
A[j1 ] ← A[j]; j1 ← j1 − 1; A[j] ← A[j1 ];
16
else if A[j] < p then
17
break inner while
18
if i ≥ j then
19
break outer while
20
j ← j − 1;
21
A[i1 ] ← A[j]; A[j1 ] ← A[i];
22
i1 ← i1 + 1; j1 ← j1 − 1;
23
A[i] ← A[i1 ]; A[j] ← A[j1 ];
24 A[i1 ] ← p; A[j1 ] ← q;
25 posp ← i1 ; posq ← j1 ;

B.5. Algorithms for the Sampling Partitioning Method

The sampling method SP from Section 5 uses a mix of two classification algorithms:
“Always compare to the smaller pivot first”, and “Always compare to the larger pivot first”.
The actual partitioning method uses Algorithm 3 for the first ns = n/1024 classifications
and then decides which pivot should be used for the first comparison in the remaining
input. (This is done by comparing the two variables i and k in Algorithm 3.) If there are
more large elements than small elements in the sample it continues using Algorithm 3,
otherwise it uses Algorithm 6 below. If the input contains fewer than 1024 elements,
Algorithm 3 is used directly.
B.6. Algorithm for the Counting Strategy

Algorithm 7 is an implementation of the counting strategy from Section 6. It uses a
variable d which stores the difference of the number of small elements and the number
of large elements which have been classified so far. On average this algorithm makes
1.8n ln n + O(n) comparisons and 1.6n ln n assignments.
31

Algorithm 6 Simple Partitioning Method (smaller pivot first)
procedure SimplePartitionSmall(A, p, q, left, right, posp , posq )
1 l ← left + 1; g ← right − 1; k ← l;
2 while k ≤ g do
3
if A[k] < p then
4
swap A[k] and A[l];
5
l ← l + 1;
6
k ← k + 1;
7
else
8
if A[k] < q then
9
k ← k + 1;
10
else
11
swap A[k] and A[g]
12
g ← g − 1;
13 swap A[left] and A[l − 1];
14 swap A[right] and A[g + 1];
15 posp ← l − 1; posq ← g + 1;

Algorithm 7 Counting Strategy C
procedure C-Partition(A, p, q, left, right, posp , posq )
1 i ← left + 1; k ← right − 1; j ← i;
2 d ← 0;
. d holds the difference of the number of small and large elements.
3 while j ≤ k do
4
if d > 0 then
5
if A[j] < p then
6
swap A[i] and A[j];
7
i ← i + 1; j ← j + 1; d ← d + 1;
8
else
9
if A[j] < q then
10
j ← j + 1;
11
else
12
swap A[j] and A[k];
13
k ← k − 1; d ← d − 1;
14
else
15
while A[k] > q do
16
k ← k − 1; d ← d − 1;
17
if j ≤ k then
18
if A[k] < p then
19
rotate3(A[k], A[j], A[i]);
20
i ← i + 1; d ← d + 1;
21
else
22
swap A[j] and A[k];
23
j ← j + 1;
24 swap A[left] and A[i − 1];
25 swap A[right] and A[k + 1];
26 posp ← i − 1; posq ← k + 1;

32

C. A FAST THREE-PIVOT ALGORITHM

We give here the complete pseudocode for the three-pivot algorithm described in [Kushagra et al. 2014]. In contrast to the pseudocode given in [Kushagra et al. 2014, Algorithm
A.1.1], we removed two unnecessary bound checks (Line 5 and Line 10 in our code) and
we move misplaced elements in Lines 15–29 using less assignments. This is used in the
implementation of [Kushagra et al. 2014], as well.12 On average, this algorithm makes
1.846..n ln n + O(n) comparisons and 1.57..n ln n + O(n) assignments.
Algorithm 8 Symmetric Three-Pivot Sorting Algorithm
procedure 3-Pivot(A, left, right)
Require: right − left ≥ 2, A[left] ≤ A[left + 1] ≤ A[right]
1 p1 ← A[left]; p2 ← A[left + 1]; p3 ← A[right];
2 i ← left + 2; j ← i; k ← right − 1; l ← k;
3 while j ≤ k do
4
while A[j] < p2 do
5
if A[j] < p1 then
6
swap A[i] and A[j];
7
i ← i + 1;
8
j ← j + 1;
9
while A[k] > p2 do
10
if A[k] > p3 then
11
swap A[k] and A[l];
12
l ← l − 1;
13
k ← k − 1;
14
if j ≤ k then
15
if A[j] > p3 then
16
if A[k] < p1 then
17
rotate4(A[j], A[i], A[k], A[l]);
18
i ← i + 1;
19
else
20
rotate3(A[j], A[k], A[l]);
21
l ← l − 1;
22
else
23
if A[k] < p1 then
24
rotate3(A[j], A[i], A[k]);
25
i ← i + 1;
26
else
27
swap A[j] and A[k];
28
j ← j + 1; k ← k − 1;
29 rotate3(A[left + 1], A[i − 1], A[j − 1]);
30 swap A[left] and A[i − 2];
31 swap A[right] and A[l − 1];
32 3-Pivot(A, left, i − 3);
33 3-Pivot(A, i − 1, j − 2);
34 3-Pivot(A, j, l);
35 3-Pivot(A, l + 2, right);

12 Code

made available by Alejandro López-Ortiz.

33

Comparisons /n ln n

1.9
1.8
1.7
1.6
1.5
QS
S
SP

1.4
8

10

12

14

16

18

20

22

Y
C
L
24

26

28

30

Items [log2 (n)]
Fig. 5. Average comparison count (scaled by n ln n) needed to sort a random input of up to n = 229 integers.
We compare classical quicksort (QS), Yaroslavskiy’s algorithm (Y), the sampling algorithm (SP), the counting
algorithm (C), the modified version of Sedgewick’s algorithm (S), and algorithm L. Each data point is the
average over 400 trials.

Comparisons /n ln n

1.6

1.4

QS
S
C
L

1.2

Y
Y0
SP
L0

1
8

10

12

14

16

18

20

22

24

26

28

30

Items [log2 (n)]
Fig. 6. Average comparison count (scaled by n ln n) needed to sort a random input of up to n = 229 integers.
We compare classical quicksort (QS) with the Median-of-3 strategy, Yaroslavskiy’s algorithm (Y), the sampling
algorithm (SP), the counting algorithm (C), the modified version of Sedgewick’s algorithm from Section 4
(S), and algorithm L. Each of these dual-pivot algorithms uses the tertiles in a sample of size 5 as the two
pivots. Moreover, L0 is an implementation of strategy L which uses the third- and sixth-largest element from
a sample of size 11. Y 0 is Yaroslavskiy’s algorithm choosing the tertiles of a sample of size 11 as the two pivots.
Each data point is the average over 400 trials.

34

Time /n ln n [ns]

4.8

QS
C
L

Y
SP
K

24

26

4.6
4.4
4.2
4
3.8
12

14

16

18

20

22

28

Items [log2 (n)]
Fig. 7. Running time experiments in C++, setting 1 with compiler flags: -O2. Each data point is the average
over 1000 trials. Times are scaled by n ln n.

5.2

Time /n ln n [ns]

5

QS
C
L

Y
SP
K

24

26

4.8
4.6
4.4
4.2
4
3.8

12

14

16

18

20

22

28

Items [log2 (n)]
Fig. 8. Running time experiments in C++, setting 2 with compiler flags: -O2 -funroll-loops. Each data point
is the average over 1000 trials. Times are scaled by n ln n.

35

7.5

Time /n ln n [ns]

7
QS

Y

C

SP

L

K

6.5

6

5.5

14

16

18

20

22

24

26

Items [log2 (n)]
Fig. 9. Running time experiments in Java 8. For warming up the JIT, we let each algorithm sort 10 000
inputs consisting of 100 000 elements. Each data point is the average over 500 trials. Times are scaled by
n ln n.

36

