Pivot Sampling in QuickXSort: Precise
Analysis of QuickMergesort and QuickHeapsort
Sebastian Wild∗

arXiv:1803.05948v1 [cs.DS] 15 Mar 2018

March 19, 2018

Abstract: QuickXSort is a strategy to combine Quicksort with another sorting
method X, so that the result has essentially the same comparison cost as X in
isolation, but sorts in place even when X requires a linear-size buffer. We solve the
recurrence for QuickXSort precisely up to the linear term including the optimization
to choose pivots from a sample of k elements. This allows to immediately obtain
overall average costs using only the average costs of sorting method X (as if run in
isolation). We thereby extend and greatly simplify the analysis of QuickHeapsort
and QuickMergesort with practically efficient pivot selection, and give the first tight
upper bounds including the linear term for such methods.

1. Introduction
In QuickXSort [5], we use the recursive scheme of ordinary Quicksort, but instead of doing
two recursive calls after partitioning, we first sort one of the segments by some other sorting
method X. Only the second segment is recursively sorted by QuickXSort. The key insight is
that X can use the second segment as a temporary buffer for elements. By that, QuickXSort
is sorting in-place (using O(1) words of extra space) even when X itself is not.
Of course, not every method is a suitable X since we may only use the temporary memory
for elements in the list in a swap-like fashion: After we are done with sorting our segment, the
elements originally stored in our buffer must still be intact, i.e., still appear in the buffer in
some order. Two examples that use extra space in such a way are (standard) Mergesorts and
the comparison-efficient Heapsort variant [1] with an output buffer. With QuickXSort we can
make those methods sort in-place while retaining their comparison efficiency. Note however
that QuickXSort is in general not stable even if X was.
While other comparison-efficient in-place sorting methods are known (e.g. [15, 9, 8]), the
ones based on QuickXSort and elementary methods X are particularly easy to implement1
since one can adapt existing implementations for X. In such an implementation, the tried and
tested optimization to choose the pivot as the median of a small sample suggests itself to
improve QuickXSort. In previous works, the influence of QuickXSort on the performance of
X was either studied by ad-hoc techniques that do not easily apply with pivot sampling or it
√
was studied for the case of very good pivots: exact medians or medians of a sample of n
∗
1

David R. Cheriton School of Computer Science, University of Waterloo, Email: wild @ uwaterloo.ca
See for example the code for QuickMergesort that was presented for discussion on code review stack exchange:
https://codereview.stackexchange.com/q/149443

2

Pivot Sampling in QuickXSort: Precise Analysis of QuickMergesort and QuickHeapsort

elements. Both are typically detrimental to the average performance since they add significant
overhead, whereas most of the benefit of sampling is realized already for samples of very small
constant sizes like 3, 5 or 9.
The contribution of this paper is a general transfer theorem (Theorem 5.1) that
expresses the costs of QuickXSort with median-of-k sampling (for any odd constant
k) directly in terms of the costs of X, (i.e., the costs that X needs to sort n elements
in isolation). We thereby obtain the first analyses of QuickMergesort and QuickHeapsort with
best possible constant-coefficient bounds on the linear term under realistic sampling schemes.
Since Mergesort only needs a buffer for one of the two runs, QuickMergesort should not
simply give Mergesort the smaller of the two segments to sort, but rather the largest one for
which the other segments still offers sufficient buffer space. (This will be the larger segment
of the two if the smaller one contains at least a third of the elements.) Our transfer theorem
covers this refined version of QuickMergesort, as well, which had not been analyzed before.2
The rest of the paper is structured as follows: In Section 2, we summarize previous work
on QuickXSort with a focus on contributions to its analysis. Section 3 collects mathematical
facts and notations used later. In Section 4 we define QuickXSort and formulate a recurrence
for its cost. Its solution is stated in Section 5 and proven in the course of Sections 7 and 8.
In Section 9, we apply our result to QuickHeapsort and QuickMergesort and discuss some
algorithmic implications.

2. Previous Work
The idea to combine Quicksort and a secondary sorting method was suggested by Contone and
Cincotti [2, 1]. They study Heapsort with an output buffer (external Heapsort),3 and combine
it with Quicksort to QuickHeapsort. They analyze the average costs for external Heapsort in
isolation and use a differencing trick for dealing with the QuickXSort recurrence; however, this
technique is hard to generalize to median-of-k pivots.
Diekert and Weiß [3] suggest optimizations for QuickHeapsort (some of which need extra
space again), and they give better upper bounds for QuickHeapsort with random pivots and
median-of-3. Their results are still not tight since they upper bound the total cost of all
Heapsort calls together (using ad hoc arguments on the form of the costs for one Heapsort
round), without taking the actual subproblem sizes into account that Heapsort is used on. In
particular, their bound on the overall contribution of the Heapsort calls does not depend on
the sampling strategy.
Edelkamp and Weiß [5] explicitly describe QuickXSort as a general design pattern and,
√
among others, consider using Mergesort as ‘X’. They use the median of n elements in each
round throughout to guarantee good splits with high probability. They show by induction
that when X uses at most n lg n + cn + o(n) comparisons on average for some constant c, the
number of comparisons in QuickXSort is also bounded by n lg n + cn + o(n). By combining
QuickMergesort with Ford and Johnson’s MergeInsertion [7] for subproblems of logarithmic
size, Edelkamp and Weiß obtained an in-place sorting method that uses on the average a close
to minimal number of comparisons of n lg n − 1.3999n + o(n).
√
Edelkamp and Weiß do consider this version of QuickMergesort [5], but only analyze it for median-of- n
pivots. In this case the behavior coincides with the simpler strategy to always sort the smaller segment by
Mergesort since the segments are of almost equal size with high probability.
3
Not having to store the heap in a consecutive prefix of the array allows to save comparisons over classic
in-place Heapsort: After an delete-max operation, we can fill the gap at the root of the heap by promoting
the largest child and recursively moving the gap down the heap. (We then fill the gap with a −∞ sentinel
value). That way, each delete-max needs exactly blg nc comparisons.
2

3. Preliminaries

3

3. Preliminaries
A comprehensive list of used notation is given in Appendix A; we mention the most important
here. We use Iverson’s bracket [stmt] to mean 1 if stmt is true and 0 otherwise. P[E] denotes
D
the probability of event E, E[X] the expectation of random variable X. We write X =
Y to
denote equality in distribution.
D
We heavily use the beta distribution: For α, β ∈ R>0 , X
=
Beta(α, β) if X admits the
R
density fX (z) = z α−1 (1 − z)β−1 /B(α, β) where B(α, β) = 01 z α−1 (1 − z)β−1 dz is the beta
function. Moreover we use the beta binomial distribution, which is a conditional binomial
D
distribution with the success probability
being a beta distributed random variable. If X =

BetaBin(n, α, β) then P[X = i] = ni B(α + i, β + (n − i))/B(α, β). For a collection of its
properties see [20], Section 2.4.7; one property that we use here is a local limit law showing that
the normalized beta binomial distribution converges to the beta distribution. It is reproduced
as Lemma C.1 in the appendix.
For solving recurrences, we build upon Roura’s master theorems [17]. The relevant continuous master theorem is restated in the appendix (Theorem B.1).

4. QuickXSort
Let X be a sorting method that requires buffer space for storing at most bαnc elements (for
α ∈ [0, 1]) to sort n elements. The buffer may only be accessed by swaps so that once X has
finished its work, the buffer contains the same elements as before (but in arbitrary order).
Then we can combine4 X with Quicksort as follows: We first randomly choose a pivot and
partition the input around that pivot. This results in two contiguous segments containing the
J1 elements that are smaller than the pivot5 and the J2 elements that are larger than the
pivot, respectively. We exclude the space for the pivot, so J1 + J2 = n − 1; note that since the
rank of the pivot is random, so are the segment sizes J1 and J2 . We then sort one segment by
X using the other segment as a buffer, and afterwards sort the buffer segment recursively by
QuickXSort.
To guarantee a sufficiently large buffer for X when it sorts Jr (r = 1 or 2), we must make
sure that J3−r ≥ αJr . In case both segments could be sorted by X, we use the larger one. The
motivation behind this is that we expect an advantage from reducing the subproblem size for
the recursive call as much as possible.
We consider the practically relevant version of QuickXSort, where we use as pivot the
median of a sample of k = 2t + 1 elements, where t ∈ N0 is constant w.r.t. n. Setting t = 0
corresponds to choosing pivots uniformly at random.

4.1. Recurrence for Expected Costs
Let c(n) be the expected number of comparisons in QuickXSort on arrays of size n and x(n)
be (an upper bound for) the expected number of comparisons in X. We will assume that x(n)
fulfills
x(n) = an lg n + bn ± O(n1−ε ),

(n → ∞),

for constants a, b and ε ∈ (0, 1].
4

Depending on details of X, further precautions might have to be taken, e.g., in QuickHeapsort [1]. In this
paper, we assume those have already been taken care of and solely focus on the analysis of QuickXSort.
5
We assume in this paper throughout that the input contains pairwise distinct elements.

4

Pivot Sampling in QuickXSort: Precise Analysis of QuickMergesort and QuickHeapsort

For α < 1, we obtain two cases: When the split induced by the pivot is “uneven” – namely
n−1
when min{J1 , J2 } < α max{J1 , J2 }, i.e., max{J1 , J2 } > 1+α
– the smaller segment is not large
enough to be used as buffer. Then we can only assign the large segment as a buffer and run X
n−1
on the smaller segment. If however the split is about “even”, i.e., both segments are ≤ 1+α
we
can sort the larger of the two segments by X. These two cases also show up in the recurrence
of costs:
c(0) = c(1) = 0
c(n) =

h

1
1+α (n

− 1)][J1 > J2 ](x(J1 ) + c(J2 ))

h

1
1+α (n

− 1)][J1 ≤ J2 ](x(J2 ) + c(J1 ))

(n − 1) + E [J1 , J2 ≤
+ E [J1 , J2 ≤

=

i

+ E [J2 >

h

1
1+α (n

− 1)](x(J1 ) + c(J2 ))

h

1
1+α (n

− 1)](x(J2 ) + c(J1 ))

+ E [J1 >
2
X

i

i
i

(n ≥ 2)

E[Ar (Jr )c(Jr )] + t(n)

(1)

r=1

where
A1 (J1 ) = [J1 , J2 ≤
A2 (J2 ) = [J1 , J2 ≤

1
1+α (n
1
1+α (n

− 1)] · [J1 ≤ J2 ] + [J1 >
− 1)] · [J1 > J2 ] + [J2 >

1
1+α (n
1
1+α (n

− 1)]
− 1)]

t(n) = (n − 1) + E[A2 (J2 )x(J1 )] + E[A1 (J1 )x(J2 )]
The expectation here is taken over the choice for the random pivot, i.e., over the segment
sizes J1 resp. J2 . Note that we use both J1 and J2 to express the conditions in a convenient
form, but actually either one is fully determined by the other via J1 + J2 = n − 1. Note how
A1 and A2 change roles in recursive calls and toll functions, since we always sort one segment
recursively and the other segment by X.
Distribution of Subproblem Sizes. If pivots are chosen as the median of a random sample
D
of size k = 2t + 1, the subproblem sizes have the same distribution, J1 =
J2 . Without pivot
D
sampling, we have J1 =
U[0..n − 1], a discrete uniform distribution. If we choose pivots as
medians of a sample of k = 2t + 1 elements, the value for J1 consists of two summands:
J1 = t + I1 . The first summand, t, accounts for the part of the sample that is smaller than
the pivot. Those t elements do not take part in the partitioning round (but they have to be
included in the subproblem). I1 is the number of elements that turned out to be smaller than
the pivot during partitioning.
D
This latter number I1 is random, and its distribution is I1 =
BetaBin(n − k, t + 1, t + 1), a
so-called beta-binomial distribution. The connection to the beta distribution is best seen by
assuming n independent and uniformly in (0, 1) distributed reals as input. They are almost
surely pairwise distinct and their relative ranking is equivalent to a random permutation of [n],
so this assumption is w.l.o.g. for our analysis. Then, the value P of the pivot in the first
partitioning step has a Beta(t + 1, t + 1) distribution by definition. Conditional on that value
D
P = p, I1 =
Bin(n − k, p) has a binomial distribution; the resulting mixture is the so-called
beta-binomial distribution.
Note that with t = 0 (no sampling) t + BetaBin(n − k, t + 1, t + 1) = BetaBin(n − 1, 1, 1)
which coincides with U[0..n − 1].

5. The Transfer Theorem

5

5. The Transfer Theorem
We now state the main result of the paper: an asymptotic approximation for c(n).
Theorem 5.1 (Total Cost of QuickXSort): The expected number of comparisons needed
to sort a random permutation with QuickXSort using median-of-k pivots, k = 2t + 1, and a
sorting method X that needs a buffer of bαnc elements for some constant α ∈ [0, 1] to sort
n elements and requires on average x(n) = an lg n + bn ± O(n1−ε ) comparisons to do so as
n → ∞ for some ε ∈ (0, 1] is


c(n) = an lg n +

1
Hk+1 − Ht+1
−a·
+ b · n ± O(n1−ε + log n),
H
H ln 2


where
α (t + 2, t + 1) + I 1
H = I0, 1+α
,

1
2 1+α

(t + 2, t + 1)

is the expected relative subproblem size that is sorted by X.
Here Ix,y (α, β) is the regularized incomplete beta function
Ix,y (α, β) =

Z y α−1
z
(1 − z)β−1
x

B(α, β)

dz,

(α, β ∈ R+ , 0 ≤ x ≤ y ≤ 1).

We prove Theorem 5.1 in Sections 7 and 8. To simplify the presentation, we will restrict
ourselves to a stereotypical algorithm for X and its value α = 12 ; the given arguments, however,
immediately extend to the general statement above.

6. QuickMergeSort
A natural candidate for X is Mergesort: It is comparison-optimal up to the linear term (and
quite close to optimal in the linear term), and needs a Θ(n)-element-size buffer for practical
implementations of merging.6
Using classical top-down or bottom-up Mergesort as described in any algorithms textbook
(e.g. [19]), we can get along with α = 12 using the following memory layout for merges: We
move the first run into the buffer and then merge it with the second run – which is still stored
in the original array – into the empty slot left by the first run. By the time this first half is
filled, we either have consumed enough of the second run to have space to grow the merged
result, or the merging was trivial, i.e., all elements in the first run were smaller.

6.1. Average Case of Mergesort
The average number of comparisons for Mergesort has the same – optimal – leading term n lg n
as in the worst and best case; and this is true for both the top-down and bottom-up variants.
The coefficient of the linear term of the asymptotic expansion, though, is not a constant, but
a bounded periodic function with period lg n, and the functions differs for best, worst, and
average case and the variants of Mergesort [18, 6, 14].
In this paper, we will confine ourselves to an upper bound for the average case x(n) =
an lg n + bn ± O(n1−ε ) with constant b valid for all n, so we will set b to the supremum of
6

Merging can be done in place using more advanced tricks (see, e.g., [12]), but those tend not to be competitive
in terms of running time with other sorting methods. By changing the global structure, an in-place Mergesort
variant can be achieved using part of the input as buffer, not unlike we do it in QuickMergesort [10]. For
that, we use that in merging runs of unequal lengths, it suffices to move the smaller of the two to a buffer.

6

Pivot Sampling in QuickXSort: Precise Analysis of QuickMergesort and QuickHeapsort

the periodic function. We leave the interesting challenge open to trace the precise behavior of
the fluctuations through the recurrence, where Mergesort is used on a logarithmic number of
subproblems with random sizes.
We thus have the following upper bounds for top-down [6] and bottom-up [14] Mergesort7
xtd (n) = n lg n − 1.24n ± O(1)

and

(2)

xbu (n) = n lg n − 0.26n ± O(1).

(3)

7. Solving the Recurrence: Leading Term
α
1
We start with Equation (1). Since α = 12 for our Mergesort, we have 1+α
= 13 and 1+α
= 23 .
(The following arguments are valid for general α, including the extreme case α = 1, but in an
attempt to de-clutter the presentation, we stick to α = 21 here.) We rewrite A1 (J1 ) and A2 (J2 )
explicitly in terms of the relative subproblem size:

h1 1 i 2 i
J1
A1 (J1 ) =
∈
,
∪ ,1 ,
n−1
3 2
3

h 1 1   2 i
J2
A2 (J2 ) =
∈
,
∪ ,1 .
n−1
3 2
3




Graphically, if we show the value of J1 /(n − 1) as a point in the unit interval, the following
picture shows which subproblem is sorted recursively; (the other subproblem is sorted by
Mergesort).
A1 = 1
A2 = 1
0

A1 = 1

A2 = 1
1/2
2/3

1/3

1

Obviously, we have A1 + A2 = 1 for any choice of J1 , which corresponds to having exactly one
recursive call in QuickMergeSort.

7.1. The Shape Function
The expectations E[Ar (Jr )c(Jr )] in Equation (1) are actually finite sums over the values
0, . . . , n − 1 that J := J1 can attain. Recall that J2 = n − 1 − J1 and A1 (J1 ) + A2 (J2 ) = 1 for
D
any value of J. With J = J1 =
J2 , we find
2
X

"

E[Ar (Jr )c(Jr )] =

E

r=1

"

+ E
=

n−1
X

h 1 1 i  2 i
J
∈
,
∪ , 1 · c(J)
n−1
3 2
3

#

h 1 1   2 i
J
∈
,
∪ , 1 · c(J)
n−1
3 2
3

#

wn,j · c(j),

where

j=0
7

Edelkamp and Weiß [5] use x(n) = n lg n − 1.26n ± o(n); Knuth [11, 5.2.4–13] derived this formula under the
assumption that n is a power of 2 (a general analysis is sketched, but Knuth does not give a closed result
for general n). Flajolet and Golin [6] continued the analysis of Mergesort in more detail; in the general case,
they find that the average number of comparisons is n lg n − (1.25 ± 0.01)n ± O(1) for any n, where the linear
term oscillates in the given range of values.

7. Solving the Recurrence: Leading Term
P[J = j] ·

h

j
n−1

∈ [ 13 , 12 ] ∪ ( 23 , 1]

+ P[J = j] ·

h

j
n−1

∈ [ 13 , 12 ) ∪ ( 23 , 1]

wn,j =

=

7
i
i

j
n−1
j
n−1

∈ [ 13 , 12 ) ∪ ( 32 , 1]


2 · P[J = j]




if





otherwise

1 · P[J = j] if
0

=

1
2

We thus have a recurrence of the form required by the Roura’s continuous master theorem
(CMT) (see Theorem B.1 in Appendix B) with the weights wn,j from above (Figure 1 shows
an example how these weights look like).
0.030

0.025

0.020

0.015

0.010

0.005

20

40

60

80

100

Figure 1: wn,j for n = 101, t = 1

It remains to determine P[J = j]. Recall that we choose the pivot as the median of
k = 2t + 1 elements for a fixed constant t ∈ N0 , and the subproblem size J fulfills J = t + I
D
with I =
BetaBin(n − k, t + 1, t + 1). So we have for i ∈ [0, n − 1 − t] by definition
!

P[I = i] =

n − k B i + t + 1, (n − k − i)) + t + 1
i
B(t + 1, t + 1)



!

=

n − k (t + 1)i (t + 1)n−k−i
i
(k + 1)n−k

(For details, see [20, Section 2.4.7].) Now the local limit law for beta binomials (Lemma C.1)
says that the normalized beta binomial I/n converges to a beta variable “in density”, and the
convergence is uniform. With the beta density fP (z) = z t (1 − z)t /B(t + 1, t + 1), we thus find
by Lemma C.1 that
1
fP (j/n) ± O(n−2 ),
(n → ∞).
P[J = j] = P[I = j − t] =
n
The shift by the small constant t from (j − t)/n to j/n only changes the function value by
O(n−1 ) since fP is Lipschitz continuous on [0, 1]. (Details of that calculation are also given in
[20], page 208.)
The first step towards applying the CMT is to identify a shape function w(z) that approximates the relative subproblem size probabilities w(z) ≈ nwn,bznc for large n. With the above
observation, a natural choice is
w(z) = 2

1
3

<z<

1
2

∨ z>

2
3



z t (1 − z)t
.
B(t + 1, t + 1)

We will now show that this is indeed a suitable shape function.

8

Pivot Sampling in QuickXSort: Precise Analysis of QuickMergesort and QuickHeapsort

7.2. Approximation Quality of the Shape Function
To prove that w(z) fulfills Equation (11) on page 16, the approximation-rate criterion, we
j
consider several ranges for bznc
n−1 = n−1 separately:
bznc
n−1

•

2
< 31 and 12 < bznc
n−1 < 3 .
Here wn,bznc = 0 and so is w(z). So actual value and approximation are exactly the same.

•

bznc
1
2
< bznc
n−1 < 2 and n−1 > 3 .
Here wn,j = 2P[J = j] and w(z) = 2fP (z) where fP (z) = z t (1 − z)t /B(t + 1, t + 1) is twice
the density of the beta distribution Beta(t + 1, t + 1). Since fP is Lipschitz-continuous on
the bounded interval [0, 1] (it is a polynomial) the uniform pointwise convergence from
R (j+1)/n
w(z) dz over all j in the range by
above is enough to bound the sum of wn,j − j/n
−1
O(n ).

•

bznc
n−1

1
3

∈ { 13 , 21 , 32 }.
At these boundary points, the difference between wn,bznc and w(z) does not vanish (in
particularly 12 is a singular point for wn,bznc ), but the absolute difference is bounded.
Since this case only concerns 3 out of n summands, the overall contribution to the error
is O(n−1 ).

Together, we find that Equation (11) is fulfilled as claimed:
n−1
X
j=0

wn,j −

Z (j+1)/n

= O(n−1 )

w(z) dz

(n → ∞).

(4)

j/n

7.3. Computing the Toll Function
The next step in applying the CMT is a leading-term approximation of the toll function. We
consider a general function x(n) = an lg n + bn ± O(n1−ε ) where the error term holds for any
constant ε > 0 as n → ∞. We start with the simple observation that
J lg J = J lg( Jn ) + lg n
= n·
=
=

J
n
J
n



J
n

lg Jn +

n lg n +

J
n



J
n

lg n



lg Jn n.

(5)

n lg n ± O(n).

(6)

For the leading term of E[x(J)], we thus only have to compute the expectation of J/n, which is
essentially a relative subproblem size. In t(n), we also have to deal with the conditionals A1 (J)
resp. A2 (J), though. By approximating Jn with a beta distributed variable, the conditionals
translate to bounds of an integral. Details are given in Lemma D.1 (see Appendix). This yields
t(n) = n − 1 + E[A2 (J2 )x(J1 )] + E[A1 (J1 )x(J2 )]
= a E[A2 (J2 )J1 lg J1 ] + a E[A1 (J1 )J2 lg J2 )] ± O(n)

t+1 
· I0, 1 (t + 2, t + 1) + I 1 , 2 (t + 2, t + 1) · n lg n ± O(n)
= 2a ·
3
2 3
2t + 2
Lemma D.1 – (a)




= a I0, 1 (t + 2, t + 1) + I 1 , 2 (t + 2, t + 1) · n lg n ± O(n),
3

|

2 3

{z
ā

}

(n → ∞).

(7)

7. Solving the Recurrence: Leading Term

9

Here we use the incomplete regularized beta function
Ix,y (α, β) =

Z y α−1
z
(1 − z)β−1

B(α, β)

x

(α, β ∈ R+ , 0 ≤ x ≤ y ≤ 1)

dz,

for concise notation. (Ix,y (α, β) is the probability that a Beta(α, β) distributed random variable
falls into (x, y) ⊂ [0, 1], and I0,x (α, β) is its cumulative distribution function.)

7.4. Which Case of the CMT?
We are now ready to apply the CMT (Theorem B.1). As shown in Section 7.3, our toll function
is Θ(n log n), so we have α = 1 and β = 1. We hence compute
H = 1−

Z 1

z w(z) dz
0

Z 1

 z t+1 (1 − z)t
2 13 < z < 21 ∨ z > 23
= 1−
dz
B(t + 1, t + 1)
0
Z
 t+1 (1 − z)t
t + 1 1 1
1
2 z
dz
= 1−2
<
z
<
∨
z
>
3
2
3

k+1

B(t + 2, t + 1)

0



= 1 − I 1 , 1 (t + 2, t + 1) + I 2 ,1 (t + 2, t + 1)
3 2



3

= I0, 1 (t + 2, t + 1) + I 1 , 2 (t + 2, t + 1)
3

(8)

2 3

For any sampling parameters, we have H > 0, so the overall costs satisfy by Case 1 of Theorem B.1
c(n) ∼

t(n)
ān lg n
∼
,
H
H

(n → ∞).

(9)

7.5. Cancellations
Combining Equations (7) and (9), we find
c(n) ∼ an lg n,

(n → ∞);

since I0, 1 + I 1 , 1 + I 1 , 2 + I 2 ,1 = 1. The leading term of the number of comparisons in Quick3

3 2

2 3

3

XSort is the same as in X itself, regardless of how the pivot elements are chosen!8 This is
not as surprising as it might seem at first sight. We are typically sorting a constant fraction
of the input by X and thus only do a logarithmic number of recursive calls on a geometrically decreasing number of elements, so the linear contribution of Quicksort (partitioning and
recursion cost) is dominated by even the first call of X, which has linearithmic cost.
Relative Subproblem Sizes. The integral 01 zw(z) dz is precisely the expected relative subproblem size for the recursive call, whereas for t(n)
we are interested in Rthe subproblem that
R
is sorted using X whose relative size is given by 01 (1 − z)w(z) dz = 1 − 01 zw(z) dz. We can
thus write ā = aH.
R
The quantity 01 zw(z) dz, the average relative size of recursive calls is certainly of independent intuitive interest. While it is intuitively clear that for t → ∞, i.e., the case of exact
medians as pivots, we must have a relative subproblem size of exactly 12 , this convergence is
R

8

This remains true even if we allow asymmetric sampling, e.g., by choosing the pivot as the smallest (or any
other order statistic) of a random sample.

10

Pivot Sampling in QuickXSort: Precise Analysis of QuickMergesort and QuickHeapsort
0.70

0.65

0.60

0.55

0.50

20

Figure 2:

R1
0

40

60

80

100

zw(z) dz, the relative recursive subproblem size, as a function of t.

not apparent from the behavior for finite t: the mass of the integral 01 zw(z) dz concentrates at
z = 12 , a point of discontinuity in w(z). It is also worthy of note that the expected subproblem
size is initially larger than 12 (0.694 for t = 0), then decreases to ≈ 0.449124 around t = 20 and
then starts to slowly increase again (see Figure 2).
R

∗

∗

∗

√
Edelkamp and Weiß [5] give the above result for the case of using the median of n elements,
where we effectively have exact medians from the perspective of analysis. In this case, the
informal reasoning given above is precise, and in fact, in this case the same form of cancellations
also happen for the linear term [5, Thm. 1]. (See also the “exact ranks” result in Section 9.) We
will show in the following that for practical schemes of pivot sampling, i.e., with fixed sample
sizes, these cancellations happen only for the leadings-term approximation. The pivot sampling
scheme does affect the linear term significantly; and to measure the benefit of sampling, the
analysis thus has to continue to the next term of the asymptotic expansion of c(n).

8. Solving the Recurrence: The Linear Term
Since c(n) ∼ an lg n for any choice of t, the leading term alone does not allow to make distinctions to judge the effect of sampling schemes. To compute the next term in the asymptotic
expansion of c(n), we consider the values c0 (n) = c(n) − an lg n. c0 (n) has essentially the same
recursive structure as c(n), only with a different toll function:
c0 (n) = c(n) − an lg n
=
=

2
X




E Ar (Jr )c(Jr ) − an lg n + t(n)

r=1
2 
X

h

E Ar (Jr ) c(Jr ) − aJr lg Jr

i



+ a E Ar (Jr )Jr lg Jr





− an lg n

r=1







+ (n − 1) + E A2 (J2 ) · x(J1 ) + E A1 (J1 ) · x(J2 )
=

2
h
X



i

E Ar (Jr )c0 (Jr ) + (n − 1) − an lg n

r=1

h



h



i

+ a E A1 (J1 ) + A2 (J2 ) J1 lg J1 + b E[A2 (J2 )J1 ]
i

+ a E A2 (J2 ) + A1 (J1 ) J2 lg J2 + b E[A1 (J1 )J2 ] ± O(n1−ε )

9. Discussion

11

D
Since J1 =
J2 we can simplify

h



i

h



i

h



i

h



i

E A1 (J1 ) + A2 (J2 ) J1 lg J1 + E A2 (J2 ) + A1 (J1 ) J2 lg J2
= E A1 (J1 ) + A2 (J2 ) J1 lg J1 + E A2 (J1 ) + A1 (J2 ) J1 lg J1
h

= E J1 lg J1 ·





A1 (J1 ) + A1 (J2 ) + A2 (J1 ) + A2 (J2 )

i

= 2E[J lg J]
= 2 E[ Jn ] · n lg n + 2 ·

(5)

= n lg n −
Lemma D.1 – (b)

1
ln 2

1
J
ln 2 E[ n

ln Jn ] · n

Hk+1 − Ht+1 n ± O(n1−ε ).


Plugging this back into our equation for c0 (n), we find
c0 (n) =

2
h
X

i

E Ar (Jr )c0 (Jr ) + (n − 1) − an lg n

r=1



+ a n lg n −

1
ln 2

 

Hk+1 − Ht+1 n





+ b I0, 1 (t + 2, t + 1) + I 1 , 2 (t + 2, t + 1) · n ± O(n1−ε )
3

=

2
X

2 3

h

i

E Ar (Jr )c0 (Jr ) + t0 (n)

r=1

where
t0 (n) = b0 n ± O(n1−ε )
b0 = 1 −

a
ln 2



Hk+1 − Ht+1 + b · H

Apart from the smaller toll function t0 (n), this recurrence has the very same shape as the
original recurrence for c(n); in particular, we obtain the same shape function w(z) and the
same H > 0 and obtain
c0 (n) ∼

b0 n
t0 (n)
∼
.
H
H

8.1. Error Bound
Since our toll function is not given precisely, but only up to an error term O(n1−ε ) for a
given fixed ε ∈ (0, 1], we also have to estimate the overall influence of this term. For that
we
consider the recurrence
for c(n) again, but replace t(n) (entirely) by C · n1−ε . If ε > 0,
R 1 1−ε
R1
w(z) dz < 0 w(z) dz = 1, so we still find H > 0 and apply case 1 of the CMT. The
0 z
overall contribution of the error term is then O(n1−ε ). For ε = 0, H = 0 and case 2 applies,
giving an overall error term of O(log n).
This completes the proof of Theorem 5.1.

9. Discussion
Since all our choices for X are leading-term optimal, so will QuickXSort be. We can thus fix
a = 1 in Theorem 5.1; only b (and the allowable α) still depend on X. We then basically find
that going from X to QuickXSort adds a “penalty” q in the linear term that depends only

12

Pivot Sampling in QuickXSort: Precise Analysis of QuickMergesort and QuickHeapsort

on the sampling size (and α), but not on X. Table 1 shows that this penalty is roughly 1n
without sampling, but can be reduced drastically when choosing pivots from a sample of 3 or
5 elements. As we increase the sample size, we converge to the situation studied by Edelkamp
√
and Weiß using median-of- n, where no linear-term penalty is left [5]. Give that q is less than
0.08 already for a sample of 21 elements, these large sample versions are mostly of theoretical
interest. It is noteworthy that the improvement from no sampling to median-of-3 yields a
reduction of q by more than 50%, which is much more than its effect on Quicksort itself (where
it reduces the leading term of costs by 15 % from 2n ln n to 12
7 n ln n).

α=1
α = 12

t=0

t=1

t=2

t=3

t = 10

t→∞

1.1146
0.9120

0.5070
0.4050

0.3210
0.2526

0.2328
0.1815

0.07705
0.05956

0
0

Table 1: QuickXSort penalty. QuickXSort with x(n) = n lg n + bn yields c(n) = n lg n + (q + b)n
where q, the QuickXsort penalty, is given in the table.

In Appendix E, we apply our transfer theorem to the two most well-studied choices for X,
Heapsort and Mergesort, and compare the results to previous analyses and measured comparison counts from previous work. The results confirm that solving the QuickXSort recurrence
exactly yields much more accurate predictions for the overall number of comparisons than
previous bounds that circumvented this.
Skewed Pivots for Mergesort? For Mergesort with α = 21 the largest fraction of elements
we can sort by Mergesort in one step is 23 ; this suggests that using a slightly skewed pivot
might be beneficial, since it will increase the subproblem size for Mergesort and decrease the
size for recursive calls. Indeed, Edelkamp and Weiß allude to this variation: “With about
15% the time gap, however, is not overly big, and may be bridged with additional efforts like
skewed pivots and refined partitioning.” (the statement appears in the arXiv version of [5],
arxiv.org/abs/1307.3033). And the above mentioned stackexchange post actually chooses
pivots as the second tertile.
Our analysis above can be extended to skewed sampling schemes (omitted due to space
constraints), but to illustrate this point it suffices to pay a short visit to “wishful-thinking
land” and assume that we can get exact quantiles for free. We can show (e.g., with Roura’s
discrete master theorem [17]) that if we always pick the exact ρ-quantile of the input, for
ρ ∈ (0, 1), the overall costs are



1 + h(ρ)


n
lg
n
+
n ± O(n1−ε )
+
b


1−ρ
cρ (n) =



1 + h(ρ)


+ b n ± O(n1−ε )
n lg n +

ρ

if ρ ∈ ( 31 , 12 ) ∪ ( 23 , 1)
otherwise

for h(x) = x lg x + (1 − x) lg(1 − x). The coefficient of the linear term has a strict minimum at
ρ = 12 : Even for α = 12 , the best choice is to use the median of a sample. (The result is the same
for fixed-size samples.) For QuickMergesort, skewed pivots turn out to be a pessimization,
despite the fact that we sort a larger junk by Mergesort. One could hypothesize that the
reason is that skewed pivots significantly decrease the amount of information we obtain from
the comparisons during partitioning, but does not make partitioning any cheaper.
Multiway Partitioning More promising than skewed pivot sampling is the use of several
pivots. The resulting MultiwayQuickXSort would be able to sort all but one segment using

References

13

X and recurse on only one subproblem. Here, determining the expected subproblem sizes
becomes a challenge, in particular for α < 1; we leave this for future work.

References
[1] D. Cantone and G. Cincotti. Quickheapsort, an efficient mix of classical sorting algorithms.
Theoretical Computer Science, 285(1):25–42, aug 2002.
[2] Domenico Cantone and Gianluca Cincotti. QuickHeapsort, an efficient mix of classical
sorting algorithms. pages 150–162, 2000.
[3] Volker Diekert and Armin Weiß. QuickHeapsort: Modifications and improved analysis.
Theory of Computing Systems, 59(2):209–230, aug 2016.
[4] Ernst E. Doberkat. An average case analysis of Floyd’s algorithm to construct heaps.
Information and Control, 61(2):114–131, May 1984.
[5] Stefan Edelkamp and Armin Weiß. QuickXsort: Efficient sorting with n log n − 1.399n +
o(n) comparisons on average. In International Computer Science Symposium in Russia,
pages 139–152. Springer, 2014.
[6] Philippe Flajolet and Mordecai Golin. Mellin transforms and asymptotics. Acta Informatica, 31(7):673–696, jul 1994.
[7] Lester R. Ford and Selmer M. Johnson. A tournament problem. The American Mathematical Monthly, 66(5):387, May 1959.
[8] Viliam Geffert and Jozef Gajdoš. In-place sorting. In Ivana Černá, Tibor Gyimóthy, Juraj
Hromkovič, Keith Jefferey, Rastislav Králović, Marko Vukolić, and Stefan Wolf, editors,
SOFSEM 2011: Theory and Practice of Computer Science, pages 248–259. Springer, 2011.
[9] Jyrki Katajainen. The ultimate heapsort. In Proceedings of the Computing: The 4th Australasian Theory Symposium, volume 20 of Australian Computer Science Communications,
pages 87–96. Springer-Verlag Singapore Pte. Ltd., 1998.
[10] Jyrki Katajainen, Tomi Pasanen, and Jukka Teuhola. Practical in-place mergesort. Nordic
Journal of Computing, 3(1):27–40, 1996.
[11] Donald E. Knuth. The Art Of Computer Programming: Searching and Sorting. Addison
Wesley, 2nd edition, 1998.
[12] Heikki Mannila and Esko Ukkonen. A simple linear-time algorithm for in situ merging.
Information Processing Letters, 18(4):203–208, May 1984.
[13] Conrado Martínez and Salvador Roura. Optimal sampling strategies in Quicksort and
Quickselect. SIAM Journal on Computing, 31(3):683–705, 2001.
[14] Wolfgang Panny and Helmut Prodinger. Bottom-up mergesort—a detailed analysis. Algorithmica, 14(4):340–354, October 1995.
[15] Klaus Reinhardt. Sorting in-place with a worst case complexity of n log n−1.3n+O(log n)
comparisons and εn log n + O(1) transports. pages 489–498. 1992.

14

References

[16] Salvador Roura. Divide-and-Conquer Algorithms and Data Structures. Tesi doctoral
(Ph. D. thesis, Universitat Politècnica de Catalunya, 1997.
[17] Salvador Roura. Improved master theorems for divide-and-conquer recurrences. Journal
of the ACM, 48(2):170–205, 2001.
[18] Robert Sedgewick and Philippe Flajolet. An Introduction to the Analysis of Algorithms.
Addison-Wesley-Longman, 2nd edition, 2013.
[19] Robert Sedgewick and Kevin Wayne. Algorithms. Addison-Wesley, 4th edition, 2011.
[20] Sebastian Wild. Dual-Pivot Quicksort and Beyond: Analysis of Multiway Partitioning
and Its Practical Potential. Doktorarbeit (Ph.D. thesis), Technische Universität Kaiserslautern, 2016. ISBN 978-3-00-054669-3.

A. Notation

15

A. Notation
A.1. Generic Mathematics
N, N0 , Z, R . . . . . . . . . natural numbers N = {1, 2, 3, . . .}, N0 = N ∪ {0}, integers
Z = {. . . , −2, −1, 0, 1, 2, . . .}, real numbers R.
R>1 , N≥3 etc. . . . . . . . restricted sets Xpred = {x ∈ X : x fulfills pred}.
0.3 . . . . . . . . . . . . . . . . . repeating decimal; 0.3 = 0.333 . . . = 13 ;
numerals under the line form the repeated part of the decimal number.
ln(n), lg(n) . . . . . . . . . . natural and binary logarithm; ln(n) = loge (n), lg(n) = log2 (n).
X . . . . . . . . . . . . . . . . . . to emphasize that X is a random variable it is Capitalized.
[a, b) . . . . . . . . . . . . . . . real intervals, the end points with round parentheses are excluded, those
with square brackets are included.
[m..n], [n] . . . . . . . . . . . integer intervals, [m..n] = {m, m + 1, . . . , n}; [n] = [1..n].
[stmt], [x = y] . . . . . . . Iverson bracket, [stmt] = 1 if stmt is true, [stmt] = 0 otherwise.
Pn
Hn . . . . . . . . . . . . . . . . . nth harmonic number; Hn = i=1 1/i.
x ± y . . . . . . . . . . . . . . . x with absolute error |y|; formally the interval x ± y = [x − |y|, x + |y|]; as
with O-terms, we use one-way equalities z = x ± y instead of z ∈ x ± y.
R1
B(α, β) . . . . . . . . . . . . . the beta function, B(α, β) = 0 z α−1 (1 − z)β−1 dz
R y α−1 (1−z)β−1
Ix,y (α, β) . . . . . . . . . . . the regularized incomplete beta function; Ix,y (α, β) = x z B(α,β)
dz for
α, β ∈ R+ , 0 ≤ x ≤ y ≤ 1.
ab , ab . . . . . . . . . . . . . . . factorial powers; “a to the b falling resp. rising.”

A.2. Stochastics-related Notation
P[E], P[X = x] . . . . . . probability of an event E resp. probability for random variable X to attain
value x.
E[X] . . . . . . . . . . . . . . . expected value of X; we write E[X | Y ] for the conditional expectation of X
given Y , and EX [f (X)] to emphasize that expectation is taken w.r.t.
random variable X.
D
X=
Y . . . . . . . . . . . . . equality in distribution; X and Y have the same distribution.

U(a, b) . . . . . . . . . . . . . . uniformly in (a, b) ⊂ R distributed random variable.
Beta(α, β) . . . . . . . . . . Beta distributed random variable with shape parameters α ∈ R>0 and
β ∈ R>0 .
Bin(n, p) . . . . . . . . . . . . binomial distributed random variable with n ∈ N0 trials and success
probability p ∈ [0, 1].
BetaBin(n, α, β) . . . . . beta-binomial distributed random variable; n ∈ N0 , α, β ∈ R>0 ;

A.3. Notation for the Algorithm
n . . . . . . . . . . . . . . . . . . length of the input array, i.e., the input size.
k, t . . . . . . . . . . . . . . . . sample size k ∈ N≥1 , odd; k = 2t + 1, t ∈ N0 .
x(n), a, b . . . . . . . . . . . Average costs of X, x(n) = an lg n + bn ± O(n1−ε ).
t(n), ā, b̄ . . . . . . . . . . . . toll function t(n) = ān lg n + b̄n ± O(n1−ε )
J1 , J2 . . . . . . . . . . . . . . (random) subproblem sizes; J1 + J2 = n − 1; J1 = t + I1 ;
D
I1 , I2 . . . . . . . . . . . . . . . (random) segment sizes in partitioning; I1 =
BetaBin(n − k, t + 1, t + 1);
I2 = n − k − I1 ; J1 = t + I1

16

References

B. The Continuous Master Theorem
We restate Roura’s CMT here for convenience.
Theorem B.1 (Roura’s Continuous Master Theorem (CMT)): Let Fn be recursively
defined by

Fn =



bn ,

for 0 ≤ n < N ;


tn +

n−1
X

(10)

wn,j Fj , for n ≥ N ,

j=0

where tn , the toll function, satisfies tn ∼ Knα logβ (n) as n → ∞ for constants K 6= 0, α ≥ 0
and
β > −1. Assume there exists a function w : [0, 1] → R≥0 , the shape function, with
R1
w(z)dz
≥ 1 and
0
n−1
X

wn,j −

j=0

Z (j+1)/n

w(z) dz

= O(n−d ),

(n → ∞),

(11)

j/n

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

Z 1

z α w(z) dz, we have the following cases:

0

tn
.
H
Z 1
tn ln n
z α ln(z) w(z) dz.
2. If H = 0, then Fn ∼
with H̃ = −(β + 1)
H̃
0
1. If H > 0, then Fn ∼

3. If H < 0, then Fn = O(nc ) for the unique c ∈ R with

Z 1

z c w(z) dz = 1.

0



Theorem B.1 is the “reduced form” of the CMT, which appears as Theorem 1.3.2 in Roura’s
doctoral thesis [16], and as Theorem 18 of [13]. The full version (Theorem 3.3 in [17]) allows
us to handle sublogarithmic factors in the toll function, as well, which we do not need here.

C. Local Limit Law for the Beta Binomial Distribution
Since the binomial distribution is sharply concentrated, one can use Chernoff bounds on beta
binomial variables after conditioning on the beta distributed success probability. That already
implies that BetaBin(n, α, β)/n converges to Beta(α, β) (in a specific sense). We can obtain
stronger error bounds, though, by directly comparing the PDFs. Doing that gives the following
result; a detailed proof is given in [20], Lemma 2.38.
Lemma C.1 (Local Limit Law for Beta-Binomial, [20], Lemma 2.38):
D
Let (I (n) )n∈N≥1 be a family of random variables with beta-binomial distribution, I (n) =
BetaBin(n, α, β) where α, β ∈ {1} ∪ R≥2 , and let fB (z) be the density of the Beta(α, β)
distribution. Then we have uniformly in z ∈ (0, 1) that




n · P I = bz(n + 1)c

= fB (z) ± O(n−1 ),

(n → ∞).

That is, I (n) /n converges to Beta(α, β) in distribution, and the probability weights converge
uniformly to the limiting density at rate O(n−1 ).

D. Approximation by (Incomplete) Beta Integrals

17

D. Approximation by (Incomplete) Beta Integrals
D
Lemma D.1: Let J =
BetaBin(n − c1 , α, β) + c2 be a random variable that differs by fixed
constants c1 and c2 from a beta-binomial variable with parameters n ∈ N and α, β ∈ N≥1 .
Then the following holds

(a) For fixed constants 0 ≤ x ≤ y ≤ 1 holds


E [xn ≤ J ≤ yn] · J lg J



α
Ix,y (α + 1, β) · n lg n ± O(n),
α+β

=

(n → ∞).

The result holds also when any or both of the inequalities in [xn ≤ J ≤ yn] are strict.
(b) E[ Jn ln Jn ] =

α
α+β (Hα

− Hα+β ) ± O(n−h ) for any h ∈ (0, 1).

Proof: We start with part (a). By the local limit law for beta binomials
(Lemma C.1) it is

plausible
to expect a reasonably
small error when we replace E [xn ≤ J ≤ yn] · J lg J by


D
E [x ≤ P ≤ y] · (P n) lg(P n) where P =
Beta(α, β) is beta distributed. We bound the error
in the following.




We have E [xn ≤ J ≤ yn] · J ln J = E [xn ≤ J ≤ yn] · Jn · n ln n ± O(n) by Equation (5);


D
it thus suffices to compute E [xn ≤ J ≤ yn] · Jn . We first replace J by I =
BetaBin(n, α, β)
and argue later that this results in a sufficiently small error. We expand
bync



E [x ≤

I
n

≤ y] ·

I
n



=

X

i
n

· P[I = i]

i=dxne
bync

=

1 X i
· nP[I = i]
n i=dxne n

=

1 X i
·
n i=dxne n

=

1
1 X
·
f (i/n) ± O(n−1 ),
B(α, β) n i=dxne

bync

Lemma C.1



(i/n)α−1 (1 − (i/n))β−1
± O(n−1 )
B(α, β)



bync

where f (z) = z α (1 − z)β−1 .
Note that f (z) is Lipschitz-continuous on the bounded interval [x, y] since it is continuously
differentiable (it is a polynomial). Integrals of Lipschitz functions are well-approximated by
finite Riemann sums; see Lemma 2.12 (b) of [20] for a formal statement. We use that on the
sum above
bync

1 X
f (i/n) =
n i=dxne

Z y

f (z) dz ± O(n−1 ),

(n → ∞).

x

Inserting above and using B(α + 1, β)/B(α, β) = α/(α + β) yields


E [x ≤

I
n

≤ y] ·

I
n



=
=

Ry α
β−1 dz
x z (1 − z)

B(α, β)

± O(n−1 )

α
Ix,y (α + 1, β) ± O(n−1 );
α+β

(12)

18

References

recall that
Ix,y (α, β) =

Z y α−1
z
(1 − z)β−1

B(α, β)

x



dz = P x < P < y



denotes the regularized incomplete beta function.
Changing from I back to J has no influence on the given approximation. To compensate
for the difference in the number of trials (n − c1 instead of n), we use the above formulas for
with n − c1 instead of n; since we let n go to infinity anyway, this does not change the result.
Moreover, replacing I by I + c2 changes the value of the argument z = I/n of f by O(n−1 );
since f is smooth, namely Lipschitz-continuous, this also changes f (z) by at most O(n−1 ).
The result is thus not affected by more than the given error term:


E [x ≤

J
n

≤ y] ·

J
n





= E [x ≤

I
n

≤ y] ·

I
n



± O(n−1 )

We obtain the claim by multiplying with n lg n.
Versions with strict inequalities in [xn ≤ J ≤ yn] only affect the bounds of the sums above
by one, which again gives a negligible error of O(n−1 ).
For part (b), we follow a similar route. The function we integrate is no longer Lipschitz
continuous, but a weaker form of smoothness is sufficient to bound the difference between the
integral and its Riemann sums. Indeed, the above cited Lemma 2.12 (b) of [20] is formulated
for the weaker notion of Hölder-continuity: A function f : I → R defined on a bounded interval
I is called Hölder-continuous with exponent h ∈ (0, 1] when
∃C ∀x, y ∈ I : f (x) − f (y) ≤ C|x − y|h .
This generalizes Lipschitz-continuity (which corresponds to h = 1).
D
As above, we replace J by I =
BetaBin(n, α, β), which affects the overall result by O(n−1 ).
We compute
I

E

I
n ln n



=

n
X

i
n

ln ni · P[I = i]

i=0

=

Lemma C.1

n
1X
i
ln i ·
n i=0 n n

= −



(i/n)α−1 (1 − (i/n))β−1
± O(n−1 )
B(α, β)



n
1
1X
·
f (i/n) ± O(n−1 ),
B(α, β) n i=0

where now f (z) = ln(1/z) · z α (1 − z)β−1 . Since the derivative is ∞ for z = 0, f cannot
be Lipschitz-continuous, but it is Hölder-continuous on [0, 1] for any exponent h ∈ (0, 1):
z 7→ ln(1/z)z is Hölder-continuous (see, e.g., [20], Prop. 2.13.), products of Hölder-continuous
function remain such on bounded intervals and the remaining factor of f is a polynomial in z,
which is Lipschitz- and hence Hölder-continuous.
By Lemma 2.12 (b) of [20] we then have
n
1X
f (i/n) =
n i=0

Z 1

f (z) dz ± O(n−h )

0

Recall that we can choose h as close to 1 as we wish; this will only affect the constant hidden
by the O(n−h ). It remains to actually compute the integral; fortunately, this “logarithmic beta
integral” has a well-known closed form (see, e.g., [20], Eq. (2.30)).
Z 1
0

ln(z) · z α (1 − z)β−1 = B(α + 1, β) Hα − Hα+β



E. Accuracy of Estimates

19

Inserting above, we finally find
E[ Jn ln Jn ] = E[ nI ln nI ] ± O(n−1 )

α
=
Hα − Hα+β ± O(n−h )
α+β
for any h ∈ (0, 1).



E. Accuracy of Estimates
In this section, we compare our estimate with comparison counts reported in previous work.
In all cases, our results improve the error of approximation significantly, and they match the
reported results very well.

E.1. QuickHeapsort
The basic external Heapsort of Cantone and Cincotti [1] always traverses one path in the heap
from root to bottom and does one comparison for each edge followed, i.e., blg nc or blg nc − 1
many per deleteMax. By counting how many leaves we have on each level, Diekert and Weiß
found [3, Eq. 1]
n blg nc − 1 + 2 n − 2blg nc ± O(log n) ≤ n lg n − 0.913929n ± O(log n)




comparisons for the sort-down phase. (The constant of the linear term is 1− ln12 −lg(2 ln 2), the
supremum of the periodic function at the linear term). Using the classical heap construction
method adds on average 1.8813726n comparisons [4], so here
x(n) = n lg n + 0.967444n ± O(nε )
for any ε > 0.
Corollary E.1 (QuickHeapsort): Median-of-k = 2t + 1 QuickHeapsort using the external
Heapsort of Cantone and Cincotti [1] uses for any ε > 0
n lg n +



1
H

−

Hk+1 −Ht+1
H ln 2



+ 0.967444 · n ± O(nε )

comparisons on average.
Both [1] and [3] report averaged comparison counts from running time experiments. We
compare them in Table 2 against the estimates from our result and previous analyses. While
the approximation is not very accurate for n = 100 (for all analyses), for larger n, our estimate
is correct up to the first three digits, whereas previous upper bounds have almost one order of
magnitude bigger errors. Note that it is expected for our bound to still be on the conservative
side since we used the supremum of the periodic linear term for Heapsort.

E.2. QuickMergesort
For QuickMergesort, Edelkamp and Weiß [5] only report on average comparisons for a medianof-3 version in their Fig. 4, where the linear term is shown to be between −0.8n and −0.9n.
And indeed, with top-down Mergesort (b = −1.24) and median-of-3 pivots, we can prove that
QuickMergesort uses at most c(n) = n lg n − 0.835025n ± O(log n) comparisons on average.

20

References

Instance
2

observed

W

CC

DW

Fig. 4
Fig. 4
Fig. 4
Fig. 4
Fig. 4
Fig. 4

[1],
[1],
[1],
[1],
[1],
[1],

n = 10 ,
n = 102 ,
n = 105 ,
n = 105 ,
n = 106 ,
n = 106 ,

k
k
k
k
k
k

=1
=3
=1
=3
=1
=3

806
714
1 869 769
1 799 240
21 891 874
21 355 988

+67
+98
−600
+9 165
+121 748
+49 994

+158
—
+90 795
—
+1 035 695
—

+156
+168
+88 795
+79 324
+1 015 695
+751 581

Tab. 2
Tab. 2
Tab. 2
Tab. 2

[3],
[3],
[3],
[3],

n = 104 ,
n = 104 ,
n = 106 ,
n = 106 ,

k
k
k
k

=1
=3
=1
=3

152 573
146 485
21 975 912
21 327 478

+1 125
+1 136
+37 710
+78 504

+10 264
—
+951 657
—

+10 064
+8 152
+931 657
+780 091

Table 2: Comparison of estimates from Corollary E.1 in this paper (W), Theorem 6 of [1] (CC)
and Theorem 1 of [3] (DW); shown is the difference between estimate and observed
average.

