Improved Average Complexity for Comparison-Based Sorting
Kazuo Iwama1

Junichi Teruyama23

1

arXiv:1705.00849v1 [] 2 May 2017

RIMS, Kyoto University, Japan;
iwama@kuis.kyoto-u.ac.jp
2
National Institute of Informatics, Japan;
3
JST, ERATO, Kawarabayashi Large Graph Project, Japan;
teruyama@nii.ac.jp

Abstract
This paper studies the average complexity on the number of comparisons for sorting algorithms. Its information-theoretic lower bound is n lg n − 1.4427n + O(log n). For many efficient
algorithms, the first n lg n term is easy to achieve and our focus is on the (negative) constant
factor of the linear term. The current best value is −1.3999 for the MergeInsertion sort. Our
new value is −1.4106, narrowing the gap by some 25%. An important building block of our
algorithm is “two-element insertion,” which inserts two numbers A and B, A < B, into a sorted
sequence T . This insertion algorithm is still sufficiently simple for rigorous mathematical analysis and works well for a certain range of the length of T for which the simple binary insertion
does not, thus allowing us to take a complementary approach with the binary insertion.

1

Introduction

A majority of existing sorting algorithms, including Bubble sort, Quick sort, Heap sort, Merge sort
and Insertion sort, are so-called comparison-based sorts, in which our basic operation is a comparison of two input numbers. The complexity in terms of this measure, the number of comparisons
needed to obtain a sorted sequence, is an obvious lower bound of the running time of the algorithm.
Thus it has been a popular research topic in TCS to investigate its upper and lower bounds for
several sorting algorithms. Note that any sorting algorithm for n elements can be described as a
binary decision tree having n! leaves corresponding to all different permutations of the n elements.
The number of comparisons to obtain one of them is the number of nodes on the path from the
root to the leaf corresponding to the sequence. Therefore we have an obvious lower bound, called
an information-theoretic lower bound. Namely, any sorting algorithm needs
dlg n!e ≈ n lg n − 1.4427n + O(log n).
comparisons in the worst case.
Usually it is not very hard to obtain an upper bound of n lg n. For instance, consider the
BinaryInsertion sort that increases the length of the sorted sequence one by one using binary
insertion. Obviously we have n − 1 steps and each of them consists of at most dlg ne comparisons
(and much less for most of the steps). Thus our interest naturally comes to the constant factor for
the linear term in n. Unfortunately, however, its analysis does not seem so easy and our knowledge
is quite limited. For instance, it is at most −0.91 for Merge (and similar other) sort [5, 12] and the
current best one is −1.32 for MergeInsertion sort obtained by Ford and Johnson more than five
decades ago [3].
Our interest in this paper is the average-case complexity on the number of comparisons, which
should be easier to obtain than the worst-case complexity. In fact we do have a number of better
results; −1.26 for Merge sort [5], −1.38 for BinaryInsertion sort, and most recently −1.3999 for
MergeInsertion sort [2]. Notice that 1.3999 is some 96.98% of 1.4427, but there still exists a gap
and seeking the exact bound for this fundamental problem should be an important research goal.

1

Our Contribution We achieve 1.4034 by a new algorithm (1,2)Insertion. Furthermore
it is shown that the constant is improved to −1.4106 by combining the new algorithm with the
MergeInsertion sort. Thus we have narrowed the previous gap between 1.3999 and 1.4427 by some
25%. Our new algorithm is based on binary insertion. Recall that the BinaryInsertion sort repeats
a binary insertion of a new item into a sorted sequence of length i − 1 for i = 2 to n. Here the
performance of binary insertion itself is optimal because it constitutes an optimal decision tree of
height dlg ie. However, if i is not a power of two, this tree is not completely balanced, i.e., there is
a difference of one comparison due to the position of the inserted element. This small difference in
each step accumulates during the repeated steps and finally creates a large imbalance. This is the
reason for its relatively poor performance.
Our idea is to use a binary insertion if i is close to a power of two and to use what we call
a “two-element merge,” or 2Merge otherwise. 2Merge merges a two-element sequence (A, B),
A < B, with a sorted sequence T of length i − 2 to obtain a sorted sequence of length i. We first
insert A using a kind of binary search, meaning A is compared with an element in T whose position
is approximately 1/3 from the smallest. If A falls into the first third of T , then we use a standard
(with a bit of care) binary search, called right-heavy binary search or RHBS. The key thing here is
that the original “bad” i changes to a “good” i0 in this binary insertion. If A falls into the right
part of T , we simply recurse. Then, we insert B into T by using a standard binary search. Thus
we can reduce the imbalance of each step of insertion, which contributes to the better bound for
the whole sorting.
Due to [2], the performance of MergeInsertion differs a lot for different n and it hits a best peak
when n is about one third from the previous power-of-two number, which achieves around −1.415.
This is much better than our (1,2)Insertion (but, unfortunately, it quickly gets worse as n leaves
the best position and ends up with −1.3999 for a roughly power-of-two n). Thus here is a natural
idea: For a given sequence X of length n that is bad for MergeInsertion, select the largest value n0
that is less than n and is good for MergeInsertion. Then we use MergeInsertion sort for a length
n0 subsequence of X and insert the remaining elements using (1,2)Insertion, which in fact gives
us −1.4106.
Related Work The idea of inserting two elements into a sorted sequence is not new. [4] and
[13] claimed two exactly optimal algorithms for such a merge operation in terms of the worst-case
complexity [4] and in terms of the average-case complexity [13]. Unfortunately, both algorithms
are a bit involved and their performance analysis did not give closed formulas for the complexity.
Our 2Merge is probably not exactly optimal, but is sufficiently simple for rigorous mathematical
analysis.
The analysis of the BinaryInsertion sort by Edelkamp and Weiß [2] gives many hints to our new
analysis. They show that the average number of comparisons is
dlg ie + B(i), where B(i) = 1 −

2dlg ie
i

(1)

for a single insertion and is
n
X
i=1



1 + ln(4pn )
(dlg ie + B(i)) = n lg n + 1 − lg pn −
pn

(2)

< n lg n − 1.386n
for the entire BinaryInsertion sort, where pn = 2dlgn ne is a parameter indicating the deviation from
a power of two. Edelkamp and Weiß [2] also includes a nice survey on this topic.
Although we have few results on the worst-case complexities for asymptotically large n, we do
have a rather rich literature for small n’s. For instance, the information-theoretic bound (actually its
ceiling) cannot be achieved by any comparison-based sorting for 12 ≤ n ≤ 15. The MergeInsertion
2

sort achieves a matching upper bound for 1 ≤ n ≤ 15, but n = 16 is still open, namely there is a gap
of one between the lower and upper bounds (45 and 46, resp.) for the exact number of necessary
comparisons. It is also known that MergeInsertion is not optimal for some n’s, for instance, for
n = 47. See [1, 3, 6, 7, 8, 9, 10, 11, 14] for these results.
Notations and Assumptions. Our sorting algorithm takes a sequence of all different n
elements as input. An average complexity (or simply complexity) of a sorting algorithm Alg is the
expected number of comparisons Alg executes to sort each of n! different sequences of length n.
Note that the complexity of all sorting algorithms in this paper is written as n lg n + cn + O(log n)
for some negative constant c. It is important to mention that the value of c, that is our main issue,
periodically changes depending on n usually and we are interested in its worst (largest) value for
asymptotically large n, unless otherwise stated. We exploit the O(log n) term to make analysis
simpler. In particular we assume, without loss of generality, that n is always even throughout this
paper. Also, when summing up a cost function f (i) for i = 1 to n, an O(1/i) term in f is not
important. For notation, we write x = y ± z if |x − y| < z, where z may be a big-O notation like
x = y ± O(z). We may denote a sequence of one element (s1 ) by simply s1 .

2

Our Algorithm and Its Analysis

See Algorithms 1, 2 and 3. The main algorithm is Algorithm 1. Note that Algorithm 2 is
improved in the next section and Algorithm 1 is combined with MergeInsertion in Section 4. For a
given sequence S = (s1 , s2 , . . . , sn−1 , sn ) with an even n, (1,2)Insertion works in Round 0, Round
Algorithm 1 (1,2)Insertion(S)
Input: A (unsorted) sequence S = (s1 , s2 , ..., sn ), where n is even.
Output: Sorted sequence
Step 1: If n = 2, then sort (s1 , s2 ) with a single comparison.
Step 2: Sort S 0 = (s1 , ..., sn−2 ) by (1,2)Insertion to obtain T 0 .
Step 3: If pn ∈ [0.5511, 0.888] then insert sn−1 and sn into T 0 by calling 2Merge(sn−1 , sn , T 0 ).
Otherwise insert sn−1 into T 0 by RHBS and then sn by RHBS.
Algorithm 2 2Merge(A, B, T )
Input: A and B are numbers and T = (t1 , t2 , ..., ti−2 ) is a sorted sequence such that i is even and
i ≥ 4.
Output: Sorted sequence of length i.
Step 1. Compare A and B and swap them if A > B.
Step 2. Let α(r) = 1 − 2−r/2 . For r = 1, 2, . . . , up to 2 lg i, compare A with tdα(r)ie and go to Step
3 if A < tdα(r)ie .
Step 3. Insert A to (tdα(r−1)ie + 1, . . . , tdα(r)ie − 1) using RHBS. Suppose that A falls between t`
and t`+1 .
Step 4. Insert B to (t`+1 , . . . , ti−2 ) using RHBS.
Algorithm 3 RHBS(A, T )
Input: A is a number and T = (t1 , t2 , ..., ti ) is a sorted sequence.
Output: Sorted sequence of length i + 1.
Step 1. If i ≤ 3 × 2dlg(i+1)e−2 − 1, then let set d := 2dlg(i+1)e−2 . Otherwise, let set d := i −
2dlg(i+1)e−1 + 1.
Step 2. Let T1 = (t1 , . . . , td−1 ) and T2 = (td+1 , . . . , ti ).
Step 3. Compare A with td . If A < td , return RHBS(A, T1 ) ◦ td ◦ T2 . Otherwise, return T1 ◦
td ◦RHBS(A, T2 ).

3

2, ... up to Round n − 2. In Round 0, s1 and s2 are sorted by a single comparison to make a sorted
sequence T0 of length two. In Round i, si+1 and si+2 are inserted into Ti−2 obtained in Round
i − 2 by using (i) a single call of 2Merge or (ii) two calls of RHBS, depending on the value i.
Recall that we wish to obtain the average complexity for all different n! sequences, in other words,
we wish to obtain the expected number of comparisons assuming that each S appears uniformly
at random. It then turns out that we can also assume that the position of si+1 (and that of si+2
also) in each round is uniformly at random in the different i + 1 positions of Ti−2 that includes i
elements. Thus the overall average complexity is a simple sum of the average complexity of each
round.
We first make an analysis of 2Merge. Note that 2Merge uses RHBS which stands for RightHeavy Binary Search. Note that the number, say q, of comparisons to insert A into a sequence
T = (t1 , . . . ti ) is q0 = dlg(i + 1)e − 1 or q0 + 1 if we use the standard binary search. The feature of
RHBS is that if q = q0 + 1 for some A, then q = q0 + 1 for any A0 such that A0 > A, in other words,
the number of comparisons is monotone. This is easily realized by selecting td (to be compared with
A) in each recursion phase such that either the number of T ’s elements that is smaller than td or
the number of those that is larger than td be (a power of two)−1. Suppose for instance 8 ≤ i ≤ 15.
Then if i is 11 or less, then the first comparison is with t4 and if i is 12 or more, then the first
comparison is with ti−7 . There would be no merit of this structure if the position of A is uniformly
distributed. However, if small A’s are more likely than large A’s, there is an obvious advantage and
that provides a real merit in 2Merge. Notice that even if our improvement in each step is a small
constant, something like 0.1, that constant significantly affect the value of our constant factor of
the linear term.
In Step 2, we determine the range of the smaller element A. If the condition there (A < tdα(r)ie )
√
is met for r = 1, then the range is (t1 , . . . , td(1−1/√2)ie−1 ), where (1 − 1/ 2) ≈ 0.2929. In general,
the range is (tdα(r−1)ie+1 , . . . , tdα(r)ie−1 ) for an integer r ≥ 1, and we wish to compute the average
complexity of Step 3, i.e., the average number of comparisons to insert A into√this range. Here we
have two technical issues: (i) We introduce a parameter wr and let wr := ( 2 − 1)2−r/2 i. Note
that wr is somehow related to the size of the above range but it may not be integral. The idea is
that the complexity does not differ significantly if the size of the range differs by a small constant
and approximating the size by wr makes our job much easier. (ii) Although the positions of A
and B are uniformly at random, we now know that A < B. Therefore
the probability that A falls

between t`−1 and t` under the condition that A < B is (i − `)/ 2i . We also extend the definition
of px = 2dlgx xe for a noninteger x.
Lemma 1. Suppose that A is to be inserted to (tdα(r−1)ie+1 , . . . , tdα(r)ie−1 ) for an even i. Then
2Merge requires
!
√
√
√
10 − 6 2 3 − 2 2
2r/2
A(r) = dlg wr e + 7 − 4 2 −
+
±O
(3)
pr
p2r
i
comparisons on average at Step 3. Furthermore, the expected value of A(r) is
Pr[r = 1]A(1) + Pr[r = 2]A(2) + · · · = dlg ie + T(i),
where


− 6p1 i −


√
√
1
1
T(i) = 5 − 4 2 − + 2 +
− 3p2i −

pi 6pi

 − 4 +
3pi

1
− 23
16p2i
1
3
1
+ 13
4p2i

√

pi ∈ (1/2, 1+4 2 ],
√

√

pi ∈ ( 1+4 2 , 2+4 2 ],
pi ∈

√
( 2+4 2 , 1].

(4)

See Section 2.1 for the proof. Now we are going to Step 4 to insert B and here is our analysis
(see Section 2.2 for its proof).
4

Lemma 2. For an even i, 2Merge requires
dlg(i − 1)e + 1 −

2
1
+
+ O(1/i)
pi 3p2i

comparisons on average at Step 4.
The entire complexity of 2Merge is the sum of these two quantities in Lemmas 1 and 2 and
another two values; (+1) for comparing A and B at Step 1 and the one for the expected number
of comparisons in Step 2 that is 2 ± O(1/i) (see Appendix A). Thus the complexity of 2Merge is
dlg ie + dlg(i − 1)e + U(i) + O(1/i)
where (T(i) is equation (4))
U(i) = 1 + T(i) −

2
pi−1

+

1
.
3p2i−1

(5)

Since this is the complexity for inserting two elements, the complexity for a single insertion can be
regarded as a half of it, or
dlg ie + U(i)/2 + O(1/i).
(6)
It then turns out that by comparing this value with (1) of the BinaryInsertion, 2Merge is better
than BinaryInsertion for 0.5511 < pi < 0.888. (Note that this range is obtained by a numerical
calculation.) Thus we use 2Merge for this range of pi and RHBS for the other range. In summary
our one step complexity is

pi ∈ (1/2, 0.5511]
 B(i)
U(i)/2 + O(1/i)
pi ∈ (0.5511, 0.888]
dlg ie +

B(i)
pi ∈ (0.888, 1]
By simple calculation, this is rewritten by
dlg ie + D(pi )

(7)

where

1 − p1i



√

25

−2 2−

6


√
13
−2 2−
D(pi ) =
3

 14
√


−2 2−

3



1 − p1i

pi ∈ (1/2, 0.5511] ,

√ i
pi ∈ 0.5511, 1+4 2 ,
 √
√ i
pi ∈ 1+4 2 , 2+4 2 ,
 √
i
pi ∈ 2+4 2 , 0.888 ,

19
7
12pi + 32p2i
√
9+ 2
1
6pi + 4p2i
13
3
6pi + 8p2i

pi ∈ (0.888, 1] .

Now by using the trapezoidal rule, we have
(Z
Z
n
1
X
dlg ne
D(pi ) = 2
×
D(x)dx +
i=1

1/2

pn

)
D(x)dx

+ O(log n)

1/2

and the following theorem. (See Appendix B for details.)
Theorem 1. The complexity of (1,2)Insertion is at most n lg n − 1.40118n.

5

(8)

2.1

Proof of Lemma 1

We first prove
of thelemma, we call RHBS(A, (t`1 +1 , . . . , t`2 −1 )),
 formula (3). By
 the assumption

where `1 = (1 − 2−(r−1)/2 )i and `2 = (1 − 2−r/2 )i . For an integer `, let E` denote the event
that A falls between
t`−1 and t` . Also F denotes the event that A is inserted between t`1 and t`2 ,
S`2
namely F = `=`1 +1 E` . Let w = `2 − `1 and z = 2i − `1 − `2 − 1. Since Pr[E` ] = i−`
, we have
(2i )
Pr[F ] =

`2
X
i−`
Pr[E` ]
2(i − `)
w·z
=
.
 = i  and Pr[E` | F ] =
i
Pr[F ]
w·z
2
2
2
`=` +1
1

Let k = 2dlg we −w. By its monotonicity, RHBS requires dlg we−1 comparisons if t`1 < A < t`1 +k ,
and requires dlg we comparisons otherwise. Therefore, the average number of comparisons is dlg we−
P`1 +k 2(i−`)
P`1 +k
P`1 +k
`=`1 +1 Pr[E` | F ] =
`=`1 +1 w·z .
`=`1 +1 Pr[E` | F ], we need to calculate the summation
Observing that k/w = 1/pw − 1, we have
`X
1 +k
`=`1 +1

2(i − `)
w·z

=

k 2i − 2`1 − k − 1
·
w
z

k z+w−k
·
(∵ 2i − 2`1 − 1 = w + z)
w  z

w−k w
k
· 1+
·
=
w
w
z


1
3
1
w
=
− 1 + −2 +
− 2 ·
(9)
pw
pw
pw
z
√




Since `1 = (1 − 2−(r−1)/2 )i and `2 = (1 − 2−r/2 )i . we have w = 2−r/2 ( 2 − 1)i ± 1 and
√
√
z = 2−r/2 ( 2 + 1)i ± 1. Observe the value wz is close to 3 − 2 2, in fact the difference is bounded
as
√
√
4−2 2
2r/2
w
<
<
(∵ r ≤ 2 lg i) .
3−2 2−
z
z
i
=

Therefore, because k/w = 1/pw − 1 and −2 +

3
pw

−

1
p2w

≤ 14 , (9) continues as

!


√
1
3
1
2r/2
(∗) =
− 1 + −2 +
− 2 · 3−2 2±
pw
pw
pw
i
√
√
√
10 − 6 2 3 − 2 2 2r/2
= −7 + 4 2 +
−
±
pr
p2r
4i
Thus, the average number of comparisons is
√
√
√
10 − 6 2 3 − 2 2 2r/2
dlg we + 7 − 4 2 −
+
±
.
pw
p2w
4i

(10)

As mentioned before the statement of the lemma, we wish to replace lg w by lg wr , since there is
no obvious way of√treating the ceiling of the former that includes another ceilings for w. Now, recall
that wr = 2−r/2 ( 2 − 1)i and pr = 2dlgwwr r e . We show that it is possible to simply replace dlg we by
 r/2 
dlg wr e almost as it is: (i) If dlg we = dlg wr e holds, then because | p1w − p1r | = O 2 i , it is enough
 r/2 
to replace the last (error) term with O 2 i . (ii) Otherwise suppose that dlg we =
6 dlg wr e. Since
6

|w − wr | < 1 and w is an integer, w must be a power of two and dlg wr e must be dlg we + 1. It then
√
<
(2
2 + 2) · 2r/2 /i.
follows that pw = 1 and we can write that 1/pr = 2 − , where || = 2|wwr −w|
r
Substituting pw = 1, (10) becomes
2r/2
dlg we ±
.
4i
Substituting dlg wr e = dlg we + 1 and 1/pr = 2 − , (3) becomes
!
!
√
√ 2
2r/2
2r/2
dlg we + (2 2 − 2) + (3 − 2 2) ± O
= dlg we ± O
.
i
i
Therefore (10) i.e., the value we want to obtain can be replaced by (3) with the error term. Thus
the former part of lemma is proved.
For formula (4) we need to give the average values of dlg wr e, 1/pr and 1/p2r . Since lg i =
dlg ie + lg pi and dxe = − b−xc for any value x, we have
l
m
j
k
√
√
dlg wr e = lg i + lg( 2 − 1) − r/2 = dlg ie − r/2 − lg(pi ( 2 − 1)) .
Also, for any value x and integer m, we have

br/2c + m
br/2 + xc =
dr/2e + m
Let

x ∈ [m, m + 1/2),
x ∈ [m + 1/2, m + 1).

j
k
√
cr (pi ) = r/2 − lg(pi ( 2 − 1)) .

√
Then since lg(pi ( 2 − 1)) ∈ (−2.5, −1), we have


 br/2c + 2
cr (pi ) :=
dr/2e + 1


br/2c + 1

√

1+ 2
pi ∈ (1/2,
4 √],
√
1+ 2 2+ 2
pi ∈ ( 4√ , 4 ],
pi ∈ ( 2+4 2 , 1].

We have the following lemmas about the expected values of dr/2e and br/2e. (See Appendix C for
the proof.)
Lemma 3. E[br/2c] = 2/3 ± O(1/i) and E[dr/2e] = 4/3 ± O(1/i).
This lemma implies
√

1+ 2

pi ∈ (1/2,
 8/3
4 √],
√
1+ 2 2+ 2
[dlg
w
e]
=
dlg
ie
±
O(1/i)
−
E
7/3
pi ∈ ( 4√ , 4 ],
r


5/3
pi ∈ ( 2+4 2 , 1].
Similarly, we can obtain the expected value of 1/pr and 1/p2r as follows. (See Appendix D for
the proof.)
Lemma 4.

E[1/pr ] =









√
3 2+5
12p√
i
3+2 2
√6pi
3 2+5
6pi

pi ∈
pi ∈
pi ∈

√
(1/2, 1+4 2 ]
√
√
( 1+4 2 , 2+4 2 ]
√
( 2+4 2 , 1]



, E 1/p2r =











√
5(3+2 2)
2
48p
√i
3+2 2
6p2i √
5(3+2 2)
12p2i

Adding all those values, we can obtain (4) and the lemma is proved.
7

√

pi ∈ (1/2, 1+4 2 ]
√

√

pi ∈ ( 1+4 2 , 2+4 2 ] .
√

pi ∈ ( 2+4 2 , 1]

2.2

Proof of Lemma 2

If t`−1 < A < t` , RHBS(B, (t` , . . . , ti−2 )) is called. Since there are i − ` positions for the insertion,
dlg(i−`)e
the average number of comparisons is dlg(i − `)e + 1 − 2 i−` using the formula for the standard
, its
binary search (B ’s position is uniformly distributed). Because Pr[t`−1 < A < t` ] = i−`
(2i )
expected value is
(
)
!
i−1
i−1
i−1
X
X
X
2dlg(i−`)e
i−`
1
dlg te
dlg(i − `)e + 1 −
· i = 1 +
t dlg te −
2
× i .
i−`
2
2
t=1

`=1

t=1

Let m = dlg(i − 1)e. Then the first sum is
i−1
X

tdlg te =

t=1

d

m−1
X

2
X

i−1
X

kd +

tm

d=1 k=2d−1 +1

t=2m−1 +1

m−1
X



(i + 2m−1 )(i − 1 − 2m−1 )m
2
d=1



 

3
1 m 4 m 4
1
i
m−2
2m−2
m
m+1
=
−2
−2
·
m4 − 4 +
+ · m2 − 2
+2 +m·
2
8
3
9
9
4
 
i
1
1
2
= m
− 4m − 2m +
2
6
2
3
=

where we used
second sum:

Pm−1
d=1

3 d 1 d
d4 + d2
8
4

d · kd =
i−1
X

mkm
k−1

+

−

km+1
(k−1)2

2dlg te = 1 +

t=1

+

k
(k−1)2

m−1
X
d=1
4m

for the third equation. Next, we calculate the

22d−1 +

i−1
X

2m

t=2m−1 +1

2
+ (i − 2m−1 − 1) · 2m
6
3
1
1
= i · 2m − 4m − 2m +
3
3
= 1+

−

Therefore,
i−1
X

t dlg te −

t=1

i−1
X

!
2

dlg te

1
× i

t=1

m

=

i
2



− i · 2m + 16 4m + 21 2m +

i

2

2

= dlg(i − 1)e −
Since i is even,

3

1
pi−1

=

1
pi

1
3

2
pi−1

+

1
+ O(1/i).
3p2i−1

+ O(1/i), which completes the proof.

Improvement of 2Merge

As mentioned before, the value of α(r) is selected based on the observation that (1) the probability that A falls in the left part of T should be close to 1/2 and (2) the length of the left part
for r = 1 (which seems more important than other less happening cases for r ≥ 2) should be close
to a power of two. The previous selection is perfect in terms of (1) but is not in terms of (2) since

8

Algorithm 4 (1,2)Insertion*(S)
Input: A (unsorted) sequence S = (s1 , s2 , ..., sn ), where n is even.
Output: Sorted sequence
Step 1: If n = 2, then sort (s1 , s2 ) with a single comparison.
0
Step 2: Sort S 0 h= (s1√
, ..., sn−2√) by
i (1,2)Insertion* to obtain T .
Step 3: If pn ∈ 43 − 126 , 34 + 123 then insert sn−1 and sn into T 0 by calling 2Merge(sn−1 , sn , T 0 ).
Otherwise insert sn−1 into T 0 by RHBS and then sn by RHBS.
Algorithm 5 2Merge*(A, B, T )
Input: A and B are numbers and T = (t1 , t2 , ..., ti−2 ) is a sorted sequence such that i is even and
i ≥ 4.
Output: Sorted sequence of length i.
Step 1. Compare A and B and swap them if A > B.
Step 2. Define α(r, pi ) as Equation (11). For r = 1, 2, . . . , up to 2 lg i, compare A with tdα(r)ie and
go to Step 3 if A < tdα(r)ie .
Step 3. Insert A to (tdα(r−1)ie + 1, . . . , tdα(r)ie − 1) using RHBS. Suppose that A falls between t`
and t`+1 .
Step 4. Insert B to (t`+1 , . . . , ti−2 ) using RHBS.
α(r) does not depend on the length i of T . In this section, we put a priority to (2) by setting

1
1

(r = 2k − 1 and pi ∈ (3/4, 1]),
 1 − 2k−1 + pi 2k+1
1
1
1 − 2k − p 2k+2
(r = 2k − 1 and pi ∈ (1/2, 3/4]),
(11)
α(r, pi ) =
i

 1− 1
(r
=
2k).
2k
Note that it now depends on i and it turns out that if A falls into the left part of T for r = 1,
then the length of the left part is exactly a power of two for any i when pi ∈ (3/4, 1]. Note that for
even r, α(r, pi ) is the same as the previous α(r).
We denote the modified 2Merge as 2Merge∗ and the whole sorting algorithm as (1,2)Insertion∗ .
(See Algorithm) Our analysis, having two cases for pi ≥ 3/4 and pi < 3/4, is more involved but we
can obtain the average number of comparisons for a single step is
( 1
3
25
pi ∈ (1/2, 3/4),
2 − 4pi + 96p2i
dlg ie + B(i) ± O(1/i) +
3
13
1 − 2pi + 24p2
pi ∈ [3/4, 1].
i

As with the previous
section,
comparing this value with (1), 2Merge∗ is better than the binary
h
√
√ i
insertion for pi ∈ 34 − 126 , 43 + 123 . (Note that we did not use numerical analysis this time.) Then,
one step complexity of (1,2)Insertion∗ is
dlg ie + D∗ (pi )
where
∗

D (pi ) =



1 − p1i




 3− 7 +
2
4pi

2−




 1−

5
2pi
1
pi

+

25
96p2i
13
24p2i

pi ∈
pi ∈
pi ∈

√

6
12 ],
√
( 34 − 126 , 3/4],
√
(3/4, 34 + 123 ],
√
( 34 + 123 , 1].

(1/2, 34 −

Thus, we have
n
X
i=1

D∗ (pi ) = 2dlg ne ×

(Z

1

D∗ (x)dx +

1/2

Z

pn

1/2

9

)
D∗ (x)dx

+ O(log n)

and can obtain the following theorem. (See Appendix E for details.)
Theorem 2. The complexity of (1,2)Insertion∗ is at most n lg n − 1.4034n.
We conducted an experiment for 2Merge∗ . See Appendix F. We prepare sequences N =
(1, 2, . . . , n) for n up to 212 = 2046. Then two elements I1 and I2 are selected from N and they are
inserted into N − {I1 , I2 } using 2Merge∗ . We take the average for the number of comparisons for
all possible pairs of I1 and I2 . As one can see the result matches the analysis very well. We also
did a similar experiment for 2Merge. The result is very close and the difference is not visible in
such a graph.

4

Combination with MergeInsertion

See Fig. 1, which illustrates the performance of (1,2)Insertion, (1,2)Insertion∗ , and MergeInsertion [2] for the value of pn . As one can see, MergeInsertion is way better than ourlalgorithms
m
k
in a certain range of pn . In fact, due to [3, page 389], its best case happens for n = 23 for an
integer k, achieving a complexity of n lg n − (3 − lg 3)n + O(lg n) ≈ n lg n − 1.415n + O(lg n). This
best case can be easily included into our (1,2)Insertion∗ , as follows (see Algorithm 4): l m
k
Suppose that our input satisfies pn ≥ 2/3. Then we select the largest k such that n0 := 23 ≤ n.
Then we sort the first n0 elements by MergeInsertion. After that the remaining elements are inserted
2n
by (1,2)Insertion∗ . Since n0 = 3p
as mentioned above, the complexity of MergeInsertion for that
n
size is
4
n0 lg n0 − (3 − lg 3)n0 = n0 dlg ne −
n
3pn
and the additional comparisons in (1,2)Insertion∗ cost is
Z pn
n
X
D∗ (x)dx.
{dlg ie + D∗ (i)} = (n − n0 ) dlg ne + 2dlg ne
2/3

i=n0 +1

Summing up these two quantities, we have
Z pn
4
0
dlg ne
n dlg ne −
D∗ (x)dx
n + (n − n ) dlg ne + 2
3pn
2/3
Z pn
4
dlg ne
= n dlg ne −
n+2
D∗ (x)dx
3pn
2/3
)
(
Z pn
4
1
∗
+
D (x)dx n.
= n lg n + − lg pn −
3pn pn 2/3
0

We can use exactly the same approach for the case that pn ≤ 2/3. It turns out however that the
combined approach is worse than MergeInsertion itself for 0.638 ≤ pn ≤ 2/3. So it is better to
use only MergeInsertion for this range. See Fig. 1 for the overall performance of the combined
algorithm.
Theorem 3. The complexity of the combined algorithm is n lg n − 1.41064n.
Algorithm 6 Combination(S)
Input: A (unsorted) sequence S = (s1 , s2 , ..., sn ), where n is even.
Output: Sorted sequence
2n
Step 1: If pn ≥ 2/3, then let n0 := 3p
. Otherwise, let n0 := 3pnn .
n
0
Step 2: Sort S = (s1 , ..., sn0 ) by the MergeInsertion
sort to√obtain
T 0.
h
i
√
Step 3: For i = n0 + 2, n0 + 4, . . . , n, if pi ∈ 43 − 126 , 34 + 123 , then insert si−1 and si into T 0 by
calling 2Merge*(si−1 , si , T 0 ), otherwise insert si−1 into T 0 by RHBS and then si by RHBS.
10

-1.398

(1,2)Insertion
(1,2)Insertion*
MergeInsertion
Combined Algorithm

-1.4

Coefficient of n

-1.402
-1.404
-1.406
-1.408
-1.41
-1.412
-1.414
-1.416
0.5 0.55 0.6 0.65 0.7 0.75 0.8 0.85 0.9 0.95

1

pn

Figure 1: Performance of the algorithms

5

Final Remarks

There is the wide agreement in the community that the information-theoretic lower bound (=
−1.4427) cannot be achieved by a specific sorting algorithm; to prove or disprove it is a big open
question. Anyway, our upper bound for the average case seems quite close to the lower bound. So
attacking the worst case using the ideas in this paper may be more promising.

References
[1] Ayala-Rincón, M., De Abreu, B. T. and De Siqueira, J.: A variant of the Ford–Johnson
algorithm that is more space efficient, Information Processing Letters, Vol. 102, No. 5, pp.
201–207 (2007).
[2] S. Edelkamp and A. Weiß. QuickXsort: Efficient Sorting with n logn - 1.399n + o(n) Comparisons on Average. CSR 2014: pp. 139–152.
[3] Ford, L. R. and Johnson, S. M.: A tournament problem, The American Mathematical Monthly,
Vol. 66, No. 5, pp. 387–389 (1959).
[4] F. K. Hwang and S. Lin, Optimal merging of 2 elements with n elements, Acta Informatica
1, pp.145–158, 1971.
[5] Knuth, D. E.: The Art of Computer Programming, Volume 3: (2nd Ed.) Sorting and Searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, USA (1998).
[6] G.K. Manacher, The Ford–Johnson algorithm is not optimal, Journal of the Association for
Computing Machinery 26 (1979) 441–456.
[7] G.K. Manacher, T.D. Bui, T. Mai, Optimum combinations of sorting and merging, Journal
of the Association for Computing Machinery 36 (1989) 290–334.

11

[8] J. Schulte Mönting, Merging of 4 or 5 elements with n elements, Theoretical Computer Science
14 (1981) 19–37.
[9] Peczarski, M.: Sorting 13 Elements Requires 34 Comparisons. In Proc. 10th Annual European
Symposium on Algorithms. LNCS, vol. 2461, pp. 785–794. Springer (2002).
[10] Peczarski, M.: New results in minimum-comparison sorting, Algorithmica, Vol. 40, No. 2, pp.
133–145 (2004).
[11] Peczarski, M.: The Ford–Johnson algorithm still unbeaten for less than 47 elements, Information processing letters, Vol. 101, No. 3, pp. 126–128 (2007).
[12] H. Steinhaus, Mathematical Snapshots, New Nork, 1950, pp. 37–40.
[13] M. Thanh, V.S. Alagar, T. D. Bui, Optimal Expected-Time Algorithms for Merging. J. Algorithms 7(3): pp. 341–357, 1986.
[14] Wells, M.: Applications of a Language for Computing in Combinatorics. In Proc. 1965 IFIP
Congress, North-Holland, Amsterdam, pp. 497–498 (1966).

12

Appendix
A

Expected Number of Comparisons in Step 2

Let Fr be the event that tdα(r−1)·ie < A < tdα(r)·ie holds similar to F in Section 2.1. Recall that
√
√
wr = 2−r/2 ( 2 − 1)i. Then, we have Pr[Fr ] = wzi , where w = wr ± 1, z = 2−r/2 ( 2 + 1)i ± 1.
2(2)


1
Then it turns out that Pr[Fr ] is close to 2−r/2 with an error term O 2r/2
, in fact,
i
wz
 − 2−r
i
2 2

√
2−r i2 ± 2( 2 + 1) · 2−r/2 i ± 1
=
− 2−r

i
2 2
√
2+1
1
1
=
+
+
r
2r (i − 1)
i(i
−
1)
(i − 1)2 2


1
(∵ 1 ≤ r ≤ 2 lg i)
= O
r/2
2 i

holds. This implies that the expected value of r, i.e., the number of comparisons at Step 2 is
E[r] =

2X
lg i

r · P r[Fr ] = 2 ± O (1/i) .

r=1

B

Detailed Analysis for Theorem 1

Theorem 1 is due to the following facts:
Proposition 1. For any integers n and n0 such that 2m−1 ≤ n < n0 ≤ 2m hold and the C 1 function
f (x) : [1/2, 1] → R,
Z pn0
n0
X
m
f (x)dx ± |f (pn0 ) − f (pn )|
f (pi ) = 2 ·
(12)
pn

i=n+1

Proof. We use the trapezoidal rule: For real values a and b, an integer N , we have
(
)
Z b
N −1
f (b) + f (a) X
1
f (x)dx = h ·
+
f (a + k · h) −
· (f 0 (b) − f 0 (a)) + O(N −3 )
2
2
12h
a
i=1

where h =

Setting a = pn , b = pn0 and h = 2−m (N = (pn0 − pn )2m = n0 − n), we have
(
)
Z p n0
n0X
−n−1 
1
f (pn ) + f (pn0 )
1
i
f (x)dx =
+
f
+
+ O(1/n)
2m
2
2 2m
pn
i=1
(
)
n0 −1 
1
f (pn ) + f (pn0 ) X
i
=
+
f
+ O(1/n)
2m
2
2m

b−a
N .

n+1

=

1
2m

n0
X
i=n+1


f

i
2m


+

0

=

f (pn ) − f (pn0 )
+ O(1/n)
2m+1

n
1 X
f (pi ) + O(1/n),
2m
i=n+1

which means (12).
13

Proposition 2. For any integer n and the function f (x) : [1/2, 1] → R,
(Z
)
Z pn
n
1
X
f (pi ) = 2dlg ne ·
f (x)dx +
f (x)dx + O(log n)
1/2

i=1

1/2

holds.
Proof. Applying Proposition 1,
n
X

dlg ne−1

f (pi ) =

i=1

d

X

2
X

d=1

i=2d−1 +1

dlg ne−1

n
X

f (pi ) +

f (pi )

i=2dlg ne−1 +1

)
|f (1) − f (1/2)|
2 ·
f (x)dx ±
2d
1/2
d=1
Z pn
|f (pn ) − f (1/2)|
dlg ne
+2
·
f (x)dx ±
2dlg ne
1/2
)
(Z
Z
(

X

=

Z

d

1

1

= 2dlg ne ·

pn

f (x)dx +
1/2

f (x)dx

+ O(log n)

1/2

holds.

C

Expected values of dr/2e and br/2c

For an integer r, recall

that Fr is the event that Step 2 requires r comparisons. Also note that
1
−r
Pr[Fr ] = 2 ± O 2r/2 i .


1
term for a while. Namely, suppose that Pr[Fr ] is exactly 2−r . Then,
We ignore the ±O 2r/2
i
P2 lg i
E[br/2c] = r=1 br/2c 2−r . The sum of terms with even r can be written as
lg i
X

−2t

t2

t=1

4
4
lg i
4
= − 2 − 2 = −O
9 9i
3i
9



lg i
i2



as using
`
X

krk =

k=1

r
r`+1
r`−1 `
−
−
.
(1 − r)2 (1 − r)2
1−r

−(r−1) · 2−1 . This means that the sum of odd terms is a
For each odd r term, br/2c · 2−r = r−1
2 2
half of the sum of even ones. Thus, if Pr[Fr ] = 2−r , then





3
4
lg i
2
lg i
−O
= −O
E[br/2c] = ·
2
9
i2
3
i2


1
holds. The error term O 2r/2
of Pr[Fr ] is as much as O(1/i) because
i
2X
lg i
r=1

br/2c ·

1
2r/2

<

∞
X
r
= O (1) .
r/2
2
r=1

Therefore, the expected value of br/2c is close to 2/3 with an error O
14

1
i



.

The rest of the proof is for the analysis of E[dr/2e]. If r is odd, then dr/2e = br/2c + 1, and
dr/2e = br/2c otherwise. Adding the sum of Pr[Fr ] for odd r, we have
lg i 
X
1

4t

t=1


±O

1
2t i


=

2
−O
3

 
1
,
i

which means the expected value of br/2c is close to 4/3 with an error O

D

1
i



.

Expected Values of 1/pr , 1/p2r

Recall



 br/2c + 2
2 − 1)i
, and cr (pi ) :=
dr/2e + 1

2dlg ie−cr (pi )

br/2c + 1
√

pr =

2−r/2 (

Then, we have
1
=
pr

√

√

1+ 2
pi ∈ (1/2,
4 √],
√
1+ 2 2+ 2
pi ∈ ( 4√ , 4 ],
pi ∈ ( 2+4 2 , 1].

√
2 + 1 2r/2
1
3+2 2
2r
·
.
· c (p ) , 2 =
pi
pr
p2i
2r i
4cr (pi )

First, we give the expected value of 1/pr . As with the proof of Lemma 3, let us suppose that
P lg i −br/2c−r/2
Pr[Fr ] is exactly 2−r . Our goal is to obtain E[2−br/2c+r/2 ] = 2r=1
2
. Considering the
sum of even terms, we have
lg i
X

−2t

2

t=1

1
= −O
3

 
1
.
i

√
For odd r, 2−br/2c−r/2 = 2−(r+1)+3/2 holds. This means that the sum of odd terms is 2 2 times as
the sum of even ones. Then, we have
−br/2c+r/2

E[2

]=

2X
lg i

2

−br/2c−r/2

r=1

√
 
1
1+2 2
.
−O
=
3
i

√
. Therefore, when pi ∈ (1/2, (1 + 2)/4]
√
√
 
2 + 1 E[2−br/2c+r/2 ]
5+3 2
1
·
=
−O
,
E[1/pr ] =
pi
4
12p1
i
√
√
and when pi ∈ ((1 + 2)/4, (2 + 2)/4]
√
√
 
2 + 1 E[2−br/2c+r/2 ]
5+3 2
1
·
=
−O
.
E[1/pr ] =
pi
2
6p1
i
P lg i −dr/2e−r/2
Considering E[2−dr/2e+r/2
] = 2r=1
2
, the difference from the ‘floor’ case is that the
√
sum of odd terms is 2 times the sum of even ones. Then, we have
√
 
1+ 2
1
−dr/2e+r/2
[2
]
=
−
O
.
E
3
i
√
√
and when pi ∈ ((1 + 2)/4, (2 + 2)/4],
√
√
 
2 + 1 E[2−dr/2e+r/2 ]
3+2 2
1
·
=
−O
.
E[1/pr ] =
pi
2
6pi
i
Moreover, the error term is

P2 lg i
r=1

2−br/2c−r · O

1
i



15

=O

1
i



Next, we give the expected value of 1/p2r . Assuming that Pr[Fr ] = 2−r , we have E[2−2br/2c+r ] =
P2 lg i −2br/2c
. The sum of even terms is 31 − O(1/i). The sum of odd terms is four times the sum
r=1 2
of even ones. Noting that the error term is also O(1/i), we have
 
5
1
−2br/2c+r
.
]= ±O
E[2
3
i
√
It turns follows that when p ∈ (1/2, (1 + 2)/4]
√
√
 

 3 + 2 2 E[2−2br/2c+r ]
5(3 + 2 2)
1
2
,
·
=
±
O
1/p
=
E
r
16
i
p2i
48p2i
√
and when pi ∈ ((2 + 2)/4, 1]
√
√
 
3 + 2 2 E[2−2br/2c+r ]
5(3 + 2 2)
1
2
·
=
±O
.
E[1/pr ] =
2
2
4
i
pi
12pi
P lg i −dr/2e
Considering E[2−2dr/2e+r ] = 2r=1
2
, the difference from ‘floor’ case is that the sum of
odd terms is the same as the sum of even ones. Then, we have
 
1
2
−2dr/2e+r
.
]= ±O
E[2
3
i
√
√
and when pi ∈ ((1 + 2)/4, (2 + 2)/4],
√
√
 
3+2 2
3 + 2 2 E[2−2dr/2e+r ]
1
2
=
,
[1/p
]
=
·
−
O
E
r
2
i
p2i
6p2i
which completes the proof.

E

Proof of Theorem 2

In this section, we give the average number of comparisons that 2Merge∗ requires at Step 2 and
Step 3. There are two cases:(i) pi ∈ (3/4, 1] and (ii) pi ∈ (1/2, 3/4].

E.1

Case I: pi ∈ (3/4, 1]

Our goal is to show that the average number of comparisons for insertion of A is
 
3
3
1
dlg ie + 2 − + 2 ± O
.
pi 4pi
i
If Step 2 has made r comparisons, we call RHBS(A, tdα(r−1)ie+1 , ..., tdα(r)ie−1 ). We denote by
wr the number of candidate positions for insertion, that is, wr = dα(r, pi )ie − dα(r − 1, pi )ie.
For the case of r = 2k − 1, because
w2k−1 = α(r, pi )i − α(r − 1, pi )i ± 1 = 2dlg ie−k−1 ± 1
and w2k−1 is an integer, we have w2k−1 = p ·2ik+1 = 2dlg ie−k−1 . Since w2k−1 is the power of two,
i
RHBS requires dlg ie − k − 1 comparisons.
For the case of r = 2k, we have


i
1
w2k = k · 1 −
± 1 = 2dlg ie−k−1 · (2pi − 1) ± 1.
2pi
2
16

The value dlg w2k e is obviously dlg ie − k − 2 or dlg ie − k − 1. Let us denote i = 3 · 2dlg ie−2 + β,
where β ∈ [1, 2dlg ie−2 ]. Then, we also have
 


i
i
i
w2k = i − k − i − k−1 +
2
2
pi 2k+1

 

β
2β
dlg ie−k−2
dlg ie−k
= −3 · 2
− k − −2
− k
2
2
   
2β
β
= 2dlg ie−k−2 + k − k .
2
2
Therefore, w2k = 2dlg ie−k−2 , that is, lg w2k = dlg ie − k − 2 if β < 2k−1 , and dlg w2k e = dlg ie − k − 1
otherwise. When dlg w2k e = dlg ie − k − 1, we have


2dlg w2k e
1
2dlg ie−k−1
=
= dlg ie−k−1
± O 2k /i ,
w2k
2pi − 1
2
· (2pi − 1) ± 1
and when dlg w2k e = dlg ie − k − 2, we have


2dlg w2k e
1
=
± O 2k /i .
w2k
4pi − 2
Let zr = 2i − dα(r − 1, pi ) · ie − dα(r, pi ) · ie − 1. Since z2k = 2dlg ie−k−1 · (6pi − 1) ± 1, we have


w2k
2pi − 1
k
=
± O 2 /i .
z2k
6pi − 1
As the proof of Lemma 1, the average number of comparisons that RHBS requires for the case
of r = 2k is
!
!
!
2dlg w2k e
2dlg w2k e
w2k
·
.
∆(2k) = dlg w2k e −
−1 · 1+ 2−
w2k
w2k
z2k
When dlg w2k e = dlg ie − k − 1,


2 − 2pi
4pi − 3 2pi − 1
∆(2k) = dlg w2k e −
· 1+
·
± O(2k /i)
2pi − 1
2pi − 1 6pi − 1
2 − 2pi 10pi − 4
= dlg w2k e −
·
± O(2k /i)
2pi − 1 6pi − 1
(8pi − 3)(4pi − 3)
= dlg ie − k − 2 +
± O(2k /i).
(2pi − 1)(6pi − 1)
When dlg w2k e = dlg ie − k − 2, i < 3 · 2dlg ie−2 + 2k−1 holds. Then, pi =

3
4

+ O(2k /i). Because


 4p − 3




2dlg w2k e
1
i
−1=
− 1 ± O 2k /i =
± O 2k /i = ±O 2k /i
w2k
4pi − 2
4pi − 2
holds, we have ∆(2k) = dlg ie − k − 2 ± O(2k /i). Note that we can deal with both cases as
i −3)(4pi −3)
k
dlg ie − k − 2 + (8p
(2pi −1)(6pi −1) ± O(2 /i).
Let us denote by Fr the event that tdα(r−1,pi )·ie < A < tdα(r,pi )·ie holds. Then, we have
dα(r,pi )·ie

wr zr
i−`
Pr [Fr ] =
 =
 =
i
2 2i
`=dα(r−1,p )·ie+1 2

(

X

i

17


8pi −1
1
±
O
2
k
k+1
i·2
pi 4
(2pi −1)(6pi +1)
±O
2
4k+1 pi

r = 2k − 1,
1
i·2k



r = 2k.

Therefore, we have
lg i
X
k=1

(2pi − 1)(6pi − 1)
Pr [F2k ] =
±O
12p2i

 
1
,
i

and
3
Pr [F2k−1 ] + Pr [F2k ] = k ± O
4



1
i2k


.

Thus, the average number of comparisons that Step 2 and Step 3 require is

X

Pr[F2k−1 ] × {2k − 1 + dlg ie − k − 1}

k≥1



(8pi − 3)(4pi − 3)
Pr[F2k ] × 2k + dlg ie − k − 2 +
± O(2k /i)
(2pi − 1)(6pi − 1)
k≥1


X
X
(8pi − 3)(4pi − 3)
k
= dlg ie − 2 +
k · {Pr[F2k−1 ] + Pr[F2k ]} +
Pr[F2k ] ×
± O(2 /i)
(2pi − 1)(6pi − 1)
r≥1
k≥1
 
X 3k (2pi − 1)(6pi − 1) (8pi − 3)(4pi − 3)
1
+
×
+O
= dlg ie − 2 +
2
k
(2pi − 1)(6pi − 1)
i
4
12pi
k≥1
 
3
3
1
= dlg ie + 2 − + 2 ± O
.
pi 4pi
i
+

E.2

X

Case II: pi ∈ (1/2, 3/4]

We show that the average number of comparisons Step 3 requires is
 
3
3
1
dlg ie + 1 −
+
±O
.
2
2pi 16pi
i
Since pi < 3/4 and i ≥ 6 is even, we have dlg ie ≥ 3.
First, we give the average number of comparisons at Step 3 when r = 1. In this case, we call
RHBS(A, (t1 , . . . , tdα(1,pi )ie−1 )). Let w = dα(1, pi )ie. Then, we have


i
i
w=
−
2 8pi



= 2dlg ie ·

4pi − 1
.
8

This implies that 2dlg ie−3 < w ≤ 2dlg ie−2 , that is, dlg we = dlg ie − 2 holds since pi ∈ (1/2, 3/4]. Let
z = 2i − w − 1. The average number of comparisons that RHBS requires is
!
!
2dlg we − w
w − 2dlg we w
∆ = dlg we −
· 1+
·
,
w
w
z
because the following holds:
2dlg we
2
w
4pi − 1
=
± O(1/i),
=
± O(1/i),
w
4pi − 1
z
12pi + 1

18



−4pi + 3
8pi − 4 4pi − 1
± O(1/i)
· 1+
·
4pi − 1
4pi − 1 12pi + 1
(4pi − 3)(20pi − 3)
= dlg we +
± O(1/i)
(4pi − 1)(12pi + 1)
−16p2i − 56pi + 11
= dlg ie +
± O(1/i).
(4pi − 1)(12pi + 1)

∆ = dlg we −

3
8

We consider the case of tw < A, that is, r > 1. Let i0 = i − w = 2dlg ie 4pi8+1 . Because
· 2dlg ie < i0 ≤ 2dlg ie−1 , dlg i0 e = dlg ie − 1 holds. Moreover, we have
pi0 =

i0
2dlg i0 e

1
∈ (3/4, 1].
4

= pi +

If tw < A, the operations of Step 2 and Step 3 after the first comparison is equivalent to the
case that our insertion goes to length i0 − 2 sequence. Because pi0 ∈ (3/4, 1], we can apply the result
of Case I. Then, the average number of Step 2 and Step 3 after the first comparison is
 
 
 0
12
12
1
3
3
1
+
±O
.
+ 2 ± O 0 = dlg ie + 1 −
lg i −
2
p i0
i
4pi + 1 (4pi + 1)
i
4pi0
As with Case I, we have
Pr[F1 ] =
and

"
Pr

(4pi − 1)(12pi + 1)
± O(1/i),
64p2i

#
[

Fr = 1 − Pr[F1 ] =

r>1

(4pi + 1)2
± O(1/i).
64p2i

Therefore, adding the cost for the first comparison, the average number of comparisons at Step 2
and Step 3 is
"
# 



[
−16p2i − 56pi + 11
12
12
1 + Pr[F1 ] × dlg ie +
+ Pr
+
Fr × dlg ie + 1 −
(4pi − 1)(12pi + 1)
4pi + 1 (pi + 1)2
r>1

−16p2i

1)2

− 56pi + 11 (4pi +
+
64p2i
64p2i
3
3
= dlg ie + 1 −
+
± O(1/i).
2pi 16p2i
= dlg ie + 1 +

E.3

−

3pi + 3
3
+
± O(1/i)
16p2i
16p2i

Average Number of Comparisons for 2Merge∗

From the above arguments, adding the average number of comparisons for Step 1 and Step 4, the
new average number of comparisons for inserting i-th elements is
( 1
3
25
pi ∈ (1/2, 3/4],
2 − 4pi + 96p2i
dlg ie + B(i) ± O(1/i) +
3
13
1 − 2pi + 24p2
pi ∈ (3/4, 1].
i

Comparing
with
dlg ie + B(i), 2Merge∗ is better than the standard binary insertion when
h
√
√ i
pi ∈ 43 − 126 , 43 + 123 . Then, one step complexity of (1,2)Insertion∗ is
dlg ie + D∗ (pi )
19

where
D∗ (pi ) =



1 − p1i




 3− 7 +
2
4pi

2−




 1−

5
2pi
1
pi

+

25
96p2i
13
24p2i

pi ∈
pi ∈
pi ∈

√

6
12 ],
√
( 34 − 126 , 3/4],
√
(3/4, 34 + 123 ],
√
( 34 + 123 , 1].

(1/2, 34 −

As Section 2, we have
n
X

D∗ (pi ) = 2dlg ne ×

i=1

(Z

1

D∗ (x)dx +

Z

pn

)
D∗ (x)dx

+ O(log n)

1/2

1/2

and we obtain Theorem 2.

F

Experiments for 2insertion

See Fig.2, which illustrates our analysis and results of simulations. The symbol ‘+’ means the
average number of comparisons of simulation for each n.
The line represents the value of analysis:
( 1
3
25
pi ∈ (1/2, 3/4),
2 − 4pi + 96p2i
dlg ie + B(i) +
13
1 − 2p3 i + 24p
pi ∈ [3/4, 1].
2
i

We prepare sequences N = (1, 2, . . . , n) for n up to 212 = 2046. Then two elements I1 and I2
are selected from N and they are inserted into N − {I1 , I2 } using 2Merge∗ . We take the average
for the number of comparisons for all possible pairs of I1 and I2 . As one can see the result matches
the analysis very well. We also did a similar experiment for 2Merge. The result is very close and
the difference is not visible in such a graph.

20

22.5

Experiment
Analysis

22

Average Number of Comparisons

21.5

21

20.5

20

19.5

19

18.5

18
600

800

1000

1200

1400

1600

1800

2000

n

Figure 2: The average number of comparisons of 2Merge: Experiment and analysis

21

