Best-case Analysis of MergeSort
with an Application to the Sum of Digits Problem

arXiv:1607.04604v2 [cs.DM] 5 Dec 2016

A manuscript (MS) v2,II intended for future journal publicationI

MAREK A. SUCHENEK
California State University Dominguez Hills, Department of Computer Science,
1000 E. Victoria St., Carson, CA 90747, USA, Suchenek@csudh.edu

Abstract
An exact formula
blg nc
X
n
n
B(n) = (blg nc + 1) −
2k Zigzag ( k+1 ),
2
2
k=0

where
Zigzag(x) = min(x − bxc, dxe − x),
for the minimum number B(n) of comparisons of keys performed by MergeSort
on an n-element array is derived and analyzed. The said formula is less complex than any other known formula for the same and can be evaluated in
O(logc ) time, where c is a constant. It is shown that there is no closed-form
formula for the above. Other variants for B(n) are described as well.
Since the recurrence relation for the minimum number of comparisons of
keys for MergeSort is identical with a recurrence relation for the number
of 1s in binary expansions of all integers between 0 and n (exclusively), the
above results extend to the sum of binary digits problem.
I

c 2016 Marek A. Suchenek.
This is a longer (new Sections 7, 8, and 9 added) version v2 of the article [Suc16]
deposited at ArXive on July 15, 2016, under the same title. These new Sections contain
the detailed analytic proofs of Theorems 2.2, 3.1, and 4.1 that were not included in the
original version v1 of this article. Other than that, the current version v2 is identical with
the original version v1.
II

Preprint submitted to arXiv.org for the record as a manuscript.

December 6, 2016

M. A. Suchenek: Best-case Analysis of MergeSort (MS) v2

2

Keywords: MergeSort, sum of digits, sorting, best case.
2010 MSC: 68W40 Analysis of algorithms,
2010 MSC: 11A63 Radix representation
ACM Computing Classification
Theory of computation: Design and analysis of algorithms: Data structures
design and analysis: Sorting and searching
Mathematics of computing: Discrete mathematics: Graph theory: Trees
Mathematics of computing: Continuous mathematics: Calculus
Contents
1 Introduction

3

2 MergeSort and its best-case behavior
2.1 Recursion tree . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Best-case and its characterization B(n) . . . . . . . . . . . . .
2.3 Zigzag function . . . . . . . . . . . . . . . . . . . . . . . . . .

3
5
5
8

3 A fractal in B(n)

11

4 Computing F̃ (x) and B(n) from one another

16

5 Relationship between the best case and the worst case

18

6 The sum of digits problem

20

7 Proof of Theorem 2.2 page 8, Subsection 2.3

20

8 Proof of Theorem 3.1 page 15, Section 3

23

9 Proof of Theorem 4.1 page 17, Section 4

28

AppendixP A
A derivation of the worst-case running time
W (n) = ni=1 dlg ie of MergeSort
32
P
n+i
36
Appendix B
Proof of m−1
i=0 b m c = n

M. A. Suchenek: Best-case Analysis of MergeSort (MS) v2

3

1. Introduction
“One Picture is Worth a Thousand Words”
[An advertisement for the San Antonio Light (1918)]
Teaching undergraduate Analysis of Algorithms has been a rewarding,
although a bit taxing, experience. I was often surprised to learn that many
basic problems that clearly belong to its core syllabus had been left unanswered or partially answered. Also, it seemed a bit odd to me that many
otherwise decent texts offered unnecessarily imprecise computations1 of several rather fundamental results.
In this article, I pursue a seemingly marginal topic, the best-case behavior
of a well-known sorting algorithm MergeSort, which pursuit, however, yields
some interesting findings that could hardly be characterized as “marginal.”
It turns out that - contrary to what a casual student of this subject might
believe - computing the exact formula for the number of comparisons of keys
that MergeSort performs on any n-element array in the best case is not a
routine exercise and leads to a problem that gained some notoriety for being
a hard nut to crack analytically: the sum of digits problem. Even more
unexpectedly, a relatively straightforward2 formula for the said number of
comparisons yields an improvement of a well-known answer to this instance
of the sum of digits problem:
How many 1s appear in binary representations of all integers between (but not including) 0 and n?
2. MergeSort and its best-case behavior
A call to MergeSort inherits an n-element array A of integers and sorts
it non-decreasingly, following the steps described below.
Algorithm MergeSort 2.1. To sort an n-element array A do:
1. If n ≤ 1 then return A to the caller,
2. If n ≥ 2 then
1
2

A notable exception in this category is [SF13].
Although not quite closed-form.

M. A. Suchenek: Best-case Analysis of MergeSort (MS) v2

4

(a) pass the first b n2 c elements of A to a recursive call to MergeSort,
(b) pass the last d n2 e elements of A to another recursive call to MergeSort,
(c) linearly merge, by means of a call to Merge, the non-decreasingly
sorted arrays that were returned from those calls onto one nondecreasingly sorted array A0 ,
(d) return A0 to the caller.
A Java code of Merge is shown on the Figure 1.

Figure 1: A Java code of Merge, based on a pseudo-code from [Baa91]. Calls to Boolean
method Bcnt.incr() count the number of comps.

A typical measure of the running time of MergeSort is the number of
comparisons of keys, which for brevity I call comps, that it performs while
sorting array A. Since no comps are performed outside Merge, the running
time of MergeSort can be computed as the sum of numbers of comps performed by all calls to Merge during the execution of MergeSort. Since the
minimum number of comps performed by Merge on two list is equal to the
length of the shorter list, and any increasingly sorted array on any size N ≥ 2
produces only best-case scenarios for all subsequent calls to Merge, a rudimentary analysis of the recursion tree for MergeSort easily yields the exact
formula for the minimum number of comps for the entire MergeSort. The
problem arises when one tries to reduce the said formula, which naturally
involves long summations, to one that can be evaluated in a logarithmic
time.

M. A. Suchenek: Best-case Analysis of MergeSort (MS) v2

5

2.1. Recursion tree
The obvious recursion tree for MergeSort and sufficiently large n is shown
on Figure 2. A recursive application of the equality3

Figure 2: A sketch of the recursion 2-tree T for MergeSort for a sufficiently large n,
with levels shown on the left and the numbers of nodes shown on the right. The nodes
correspond to calls to MergeSort and show sizes of (sub)arrays passed to those calls. The
last level is h; it only contains nodes with value 1. The root corresponds to the original
call to MergeSort. If a call that is represented by a node p executes further recursive call
to MergeSort then these calls are represented by the children of p; otherwise p is a leaf.

n
n+1
d e=b
c
(1)
2
2
allows for rewriting of that tree onto one whose first four levels are shown on
Figure 3.
2.2. Best-case and its characterization B(n)
The best-case arrays of sizes b n2 c and d n2 e for Merge, where n ≥ 2, are
those in which every element of the first array is less than all elements of the
second one. In such a case, MergeSort performs b n2 c of comps.
3

It can be verified separately for odd and even values of n.

M. A. Suchenek: Best-case Analysis of MergeSort (MS) v2

6

Figure 3: The first four levels of the recursion 2-tree T from Figure 2, with the equality
(1) applied, recursively. The number of comparisons of keys performed in the best case by
Merge invoked in step 2c of Algorithm 2.1 as a result to a call to MergeSort corresponding
to a node of T is equal to the number that is shown in its left child, highlighted yellow.
k
All the right children at level k ≥ 1 of T show numbers of the form b 2n+i
k+1 c, where i ≥ 2 .
Thus all the left children (highlighted yellow) at level k ≥ 1 show numbers of the form
k
b 2n+i
k+1 c, where i < 2 .

Thus the following recurrence relation for the least number B(n) of comparisons of keys that MergeSort performs on any n-element array is straightforward to derive from its description given by Algorithm 2.1.
B(1) = 0,

(2)

and, for n ≥ 2,

n
n
n
B(n) = b c + B(b c) + B(d e).
2
2
2
Using the equality (1), the recurrence relation (3) is equivalent to:
n
n
n+1
B(n) = b c + B(b c) + B(b
c).
2
2
2

(3)

(4)

A graph of B(n) is shown on Figure 4.
Unfolding the recurrence (4) allows for noticing that the minimum number
B(n) of comps performed by all calls to Merge is equal to the sum of all values
shown at nodes highlighted yellow in the recursion tree T of Figure 3. They
may be summed-up level-by-level. One can notice from Figure 3 that the

M. A. Suchenek: Best-case Analysis of MergeSort (MS) v2

7

120
100
80
60
40
20

10

20

30

40

50

Figure 4: Graph of the solution B(n) of the recurrence (2) and (3).

number of comps performed at any level k with the maximal number 2k of
nodes is given by this formula:
k −1
2X

b

i=0

n+i
c.
2k+1

(5)

What is not clear is whether all levels of the recursion tree T are maximal.
Fortunately, the answer to this question does not depend on whether given
instance of MergeSort is running on a best-case array or on any other case
of array. It has been known form a classic analysis of the worst-case running
time of MergeSort that every level of its recursion tree T that contains at
least one non-leaf, or - in other words - a node that shows value p ≥ 2, is
maximal. Appendix A page 32 contains a detailed derivation of that fact.
Thus all levels 0 through h − 1 of T are maximal. Therefore, the formula (5)
gives the number of comps for every level 0 ≤ k ≤ h − 1.
The last level h of T may be not maximal because the level h − 1 may
contain leaves, or - in other words - nodes that show value p = 1, where
h−1
− 1, and as such do not have any children
p = b 2n+i
h−1 c for some 0 ≤ i ≤ 2
in level h. However, for each such node the value of b p2 c = b n+i
c is 0, so
2h
it can be included in summation (5) without affecting its value even though
the said value does not correspond to any node in level h. Therefore, the
formula (5) gives the number of comps for level k = h.

M. A. Suchenek: Best-case Analysis of MergeSort (MS) v2

8

Also, the depth of T is blg nc, as the Theorem Appendix A.0.2 page 35
in Appendix A states. Thus the minimum number of comps performed by
MergeSort is given by this formula:
blg nc 2k −1

X X n+i
b k+1 c.
2
k=0 i=0

(6)

Unfortunately, the summation (6) contains n−1 non-zero terms, so it cannot
be evaluated quickly in its present form. Fortunately, its inner summation
(5) can be reduced to a closed-form formula.
2.3. Zigzag function
In order to reduce (5) to a closed form, I am going to use function Zigzag
defined by:
Zigzag (n) = min(x − bxc, dxe − x).
(7)
The following fact is instrumental for that purpose.
Theorem 2.2. For every natural number n and every positive natural number
m,
m−1
2m−1
X n+i
X n+i
n
c−
b
c = 2m × Zigzag (
),
(8)
b
2m
2m
2m
i=0
i=m
where Zigzag is a function defined by (7) and visualized on Figure 5.
0.5

-0.5

0

0.5

1

1.5

2

2.5

3

3.5

4

Figure 5: Graph of function Zigzag(x) = min(x − bxc, dxe − x).

Proof. The equality (8) can be verified experimentally, for instance, with a
help of software for symbolic computation4 . The analytic proof is deferred
to Section 7.

4

I used Wolfram Mathematica for that purpose.

M. A. Suchenek: Best-case Analysis of MergeSort (MS) v2

9

Corollary 2.3. For every natural number n and every positive natural number m,
m−1
X n+i
n
n
b
c = − m × Zigzag (
),
(9)
2m
2
2m
i=0
where Zigzag is a function defined by (7) and visualized on Figure 5.
Proof. First, let’s note5 that
2m−1
X

b

i=0

n+i
c = n.
2m

(10)

From (10) I conclude
m−1
X

2m−1
X n+i
n+i
b
c+
b
c = n.
2m
2m
i=0
i=m

Solving equations (8) and (11) for

Pm−1
i=0

(11)

b n+i
c yields (9).
2m

Here is the closed-form of the summation (5).
Corollary 2.4. For every natural number n and every natural number k,
k −1
2X

i=0

b

n
n
n+i
c = − 2k Zigzag ( k+1 ),
k+1
2
2
2

(12)

where Zigzag is a function defined by (7) and visualized on Figure 5.
Proof. Substitute m = 2k in (9).
The following theorem yields the formula (13) for the minimum number
B(n) of comps performed by MergeSort.
Theorem 2.5. For every natural number n,
blg nc 2k −1

blg nc
X X n+i
X
n
n
b k+1 c = (blg nc + 1) −
2k Zigzag ( k+1 ),
2
2
2
k=0 i=0
k=0

(13)

where Zigzag is a function defined by (7) and visualized on Figure 5.
5

Analytic proof of that fact is a straightforward exercise; see Appendix Appendix B
page 36.

M. A. Suchenek: Best-case Analysis of MergeSort (MS) v2

10

Proof.
blg nc 2k −1

blg nc
X X n+i
X n
n
b k+1 c =
( − 2k Zigzag ( k+1 )) =
2
2
2
k=0 i=0
k=0
blg nc
X
n
n
2k Zigzag ( k+1 ).
= (blg nc + 1) −
2
2
k=0

140
120
100
80
60
40
20
0
10

20

30

40

50

Pblg nc P2k −1 n+i
n
Figure 6: Graphs of functions
i=0 b 2k+1 c (bottom line) and 2 (blg nc + 1) −
k=0
Pblg nc k
n
k=0 2 Zigzag ( 2k+1 ) (top line) of equality (13). They coincide with each other for all
natural numbers n.

Formula (13), although not quite closed-form, comprises of summation
with only blg nc + 1 closed-form terms, so it may be evaluated in O(logc )
time, where c is a constant. I will show in Section 3 that (13) does not have
a closed form. Graphs of both sides of equality (13) are shown on Figure 6.
Once can see that for natural numbers n they coincide with the solution B(n)
of recurrences (2) and (3) visualized on Figure 4.
Corollary 2.6. For every natural number n, the minimum number B(n) of
comps that MergeSort performs while sorting an n-element array is:
blg nc
X
n
n
2k Zigzag ( k+1 ),
B(n) = (blg nc + 1) −
2
2
k=0

where Zigzag is a function defined by (7) and visualized on Figure 5.

(14)

M. A. Suchenek: Best-case Analysis of MergeSort (MS) v2

11

3. A fractal in B(n)
A deceitfully simple expression
blg xc

X

2k+1 Zigzag (

k=0

x
2k+1

),

(15)

half of which occurs in formula (14) of Corollary 2.6, is a formidable adversary
for those who may try to turn it into a closed form, although the time required
for its evaluation for any given n is O(logc ) 6 . That does not come as a
surprise, taking into account that its graph, shown on Figure 7, bears a
resemblance of fractal. This can be easily seen as soon as a sawtooth function
2blg xc+1 − x is subtracted from it, yielding the function F (x) given by
blg xc

F (x) =

X

2k+1 Zigzag (

k=0

x
2k+1

) − 2blg xc+1 + x.

(16)

40

30

20

10

0
10

Figure 7: A graph of function
tion 2blg xc+1 − x.

Since

1
2

≤

x
2blg xc+1

20

Pblg xc
k=0

40

50

60

x
2k+1 Zigzag ( 2k+1
) plotted against a sawtooth func-

< 1, equality (7) implies
Zigzag (

6

30

x

x
)
=
1
−
,
2blg xc+1
2blg xc+1

So, to all practical purposes, (14) is a closed-form formula.

M. A. Suchenek: Best-case Analysis of MergeSort (MS) v2
or
2blg xc+1 Zigzag (

x
2blg xc+1

12

) = 2blg xc+1 − x.

(17)

The equality (17) simplifies definition (16) of function F to
blg xc

F (x) =

X

2k Zigzag (

k=1

x
),
2k

(18)

visualized on Figure 8.
30
25
20
15
10
5

10

20

30

40

50

60

Pblg xc
Figure 8: A graph of function F (x) = k=1 2k Zigzag ( 2xk ) plotted below its tight linear
x−1
1 k+1
upper bound y = x−1
+(−1)k ) for
2 (if can be shown that F (x) = 2 whenever x = 3 (2
x
k
some integer k ≥ 0); also shown below F (x) are the terms 2 Zigzag ( 2k ) of the summation
and their tight linear upper bound y = x3 .

The function F is a fractal with quasi similarity that repeats at intervals
of exponentially growing length. It is a union
F =

∞
[

fk

(19)

k=0

of functions fk , each having an interval [2k , 2k+1 ) as its domain. In other
words, for every integer k ≥ 0,
fk = F  [2k , 2k+1 ),
which, of course, yields (19).

(20)

M. A. Suchenek: Best-case Analysis of MergeSort (MS) v2

13

0.7
0.6
0.5
0.4
0.3
0.2
0.1
-0.2

0.2

0.4

0.6

0.8

1.0

1.2

Figure 9: A graph of the first six (the
P∞first 1one is2 0) normalized parts of function of
Figure 8 plotted against the line y = i=0 22i+1
= 3 . Also shown (in blue) are the first
five terms 21i Zigzag (2i x), i = 0, ..., 4, of sums that occur in the formula (24) for f˜k (x); for
each integer n and all x ∈ [n, n + 1), their parts above the X-axis restricted to [n, n + 1)
visualize a fragment of an infinite binary search trie T defined as the set of shortest binary
expansions of x − bxc with the last digit 1 (if the said binary expansion is finite) being
interpreted as the sequence terminator; in particular, the root of T is .1, and if a is a finite
binary sequence then the children of binary expansion .a1 are .a01 and .a11 .

Let fˆk be the normalized fk on interval [0, 1), defined by:
1
fˆk (x) = k fk (2k (x + 1)),
2

(21)

and f˜k be the periodized fˆk by composing it with a sawtooth function x−bxc,7
defined by:
f˜k (x) = fˆk (x − bxc).
(22)
Contracting definitions (20), (21), and (22), yields
1
f˜k (x) = k F (2k (x − bxc + 1)).
2

(23)

One can compute8 from (23) the following alternative formula for f˜k (x):
f˜k (x) =

7
8

k−1
X
1
Zigzag (2i x).
i
2
i=0

(24)

The fractional part of x.
An elementary geometric argument based on the graph visualized on Figure 9 will do.

M. A. Suchenek: Best-case Analysis of MergeSort (MS) v2

14

Figure 9 shows functions f˜0 , ..., f˜6 drawn on the same graph.
Since each function fk , and - therefore - each function fˆk , and - therefore each function f˜k , are a result of smaller and smaller triangles piled, originating
in function Zigzag of definition (18) of function F , on one another as shown
on Figure 9, for any integers 0 ≤ i < j, f˜i linearly interpolates f˜j . Because
of that, each f˜i linearly interpolates the limit F̃ of all f˜k s defined by:
F̃ (x) = lim f˜k (x),

(25)

k→∞

as Figure 10 illustrates. An application of (24) to (25) yields:
∞
X
1
Zigzag (2i x).
F̃ (x) =
i
2
i=0

(26)

0.7
0.6
0.5
0.4
0.3
0.2
0.1
-0.2

0.2

0.4

0.6

0.8

1.0

1.2

Figure 10: Functions functions f˜0 (x), f˜1 (x), ... and their limit (the topmost curve) F̃ (x)
given by (26). Collapsing the Zigzag(x) would yield the same, albeit scaled-down (by the
factor of 2) pattern 21 F̃ (2x), as (26) does imply.

Since for every integer n and i ≥ k, 2i 2nk is integer, Zigzag (2i 2nk ) = 0.
Therefore, by virtue of (24) and (26), for every non-negative integer k and
n,
n
n
F̃ ( k ) = f˜k ( k ).
(27)
2
2
This and (24) eliminate the need for infinite summation9 while computing
F̃ ( 2nk ).
9

As it appears in (26)

M. A. Suchenek: Best-case Analysis of MergeSort (MS) v2

15

It can be shown that although a continuous function, F̃ is nowheredifferentiable. As such, it does not have a closed-form formula as any closedform formula on a real interval must define a function have a derivative at
every point of that interval, except for a non-dense set of its points. Since F̃
can be expressed in function, described by a closed-form formula, of the righthand side of formula (13), the latter does not have a closed-form formula,
either.
Theorem 3.1. There is no closed-form formula ϕ(n) the values of which
Pblg nc
n
coincide with k=0 2k Zigzag ( 2k+1
), for all positive integers n, that is, for
every closed-form formula ϕ(n) on function Zigzag there is a positive n such
that
blg nc
X
n
(28)
2k Zigzag ( k+1 ) 6= ϕ(n),
2
k=0
where Zigzag is a function defined by (7) and visualized on Figure 5.
Proof. Follows from the above discussion. A more detailed proof is deferred
to Section 8.
This way I arrived at the following conclusion.
Corollary 3.2. There is no closed-form formula for B(n).
Proof. A closed-form formula for B(n) would, by virtue of (14) page 10, yield
Pblg nc
n
a closed-form formula for k=0 2k Zigzag ( 2k+1
), which by Theorem 3.1 does
not exist.
Note. One can apply the reverse transformations to those used in Section 3 on function F̃ and construct a fractal function F̆ , shown on Figure 11,
given by the equation
x
F̆ (x) = 2blg xc F̃ ( blg xc ),
(29)
2
that for every positive integer n satisfies
F̆ (n) = F (n),
where F is given by (18).

(30)

M. A. Suchenek: Best-case Analysis of MergeSort (MS) v2

16

20
15
10
5
0
10

20

30

40

50

60

Figure 11: A graph of function F̆ (x) = 2blg xc F̃ ( 2blgx xc ) plotted above a graph of the
Pblg xc
function F (x) = k=1 2k Zigzag ( 2xk ).

4. Computing F̃ (x) and B(n) from one another
Computing values of function F̃ (x) does not have to be as complex as (or
more complex than) the definition (26) implies. Of course, for every integer
n, F̃ (n) = 0. One can apply some elementary arguments based on a structure
visualized on Figure 10 to conclude that
2
1
2
F̃ ( ) = F̃ ( ) = ,
3
3
3

(31)

(the latter being the maximum of F̃ (x)) or that for every positive integer k,
F̃ (

k
1
) = k.
k
2
2

(32)

It takes a bit more work to compute
F̃ (

3
3k − 4
)=
.
k
2
2k

(33)

It turns out that computing values of function F̃ (x) for every x that has
a finite binary expansion can be done easily if an oracle for computing the
values of the function B(n) defined by (2) and (3) is given10 . Once that is
accomplished, since F̃ (x) is a continuous function and the set of numbers
with finite binary expansions is dense in the set R of reals, it allows for fast
approximations of F̃ (x) for every real x. 11

10
11

Which is not that surprising after a glance at Figure 11.
It helps to remember that F̃ is a periodic function with F̃ (x) = F̃ (x − bxc).

M. A. Suchenek: Best-case Analysis of MergeSort (MS) v2
Theorem 4.1. For every positive integer n

12

17

and integer k with n ≤ 2k ,

n
n × k − 2B(n)
)=
.
(34)
k
2
2k
Proof. The equality (34) can be verified experimentally, for instance, with a
help of software for symbolic computation4 . The analytic proof is deferred
to Section 9.
F̃ (

Theorem 4.1 allows for easy computing of B(n) if F̃ ( 2nk ) is given for some
k ≥ lg n using this form of (34):
Corollary 4.2. For every positive integer n and integer k with n ≤ 2k ,
n×k
n
B(n) =
− 2k−1 F̃ ( k ).
(35)
2
2
Proof. An obvious conclusion from (34).
For instance, putting k = blg nc + 1 in (35) easily yields (14). For k =
dlg ne we obtain
B(n) =

n
ndlg ne
− 2dlg ne−1 F̃ ( dlg ne ) =
2
2

[by (26)]
∞

X 1
ndlg ne
n
=
− 2dlg ne−1
Zigzag (2i dlg ne ) =
i
2
2
2
i=0
[since for i ≥ dlg ne, 2i 2dlgn ne is integer and Zigzag (2i 2dlgn ne ) = 0]
dlg ne−1
X 1
ndlg ne
n
dlg ne−1
=
−2
Zigzag (2i dlg ne ) =
i
2
2
2
i=0
dlg ne−1
n
ndlg ne 1 X dlg ne−i
−
2
Zigzag ( dlg ne−i ).
=
2
2 i=0
2

Substituting k for dlg ne − i we conclude
dlg ne
ndlg ne 1 X k
n
2 Zigzag ( k ),
B(n) =
−
2
2 k=1
2

a similar to (14) characterization of B(n).
12

Of course, one if free to assume that n is odd here.

(36)

M. A. Suchenek: Best-case Analysis of MergeSort (MS) v2

18

5. Relationship between the best case and the worst case
A casual student of MergeSort tends to believe that its worst-case behavior is about twice as bad as its best-case behavior. This, of course, is
only approximately true. In this Section, I will derive the exact difference
between 2B(n) and W (n) using function F defined by (16) page 11.
An exact formula for the number W (n) of comparisons of keys performed
by MergeSort in the worst case is known13 and is given for any positive
integer n by the following equality:
n
X
W (n) =
dlg ie.

(37)

i=1

From (14) and (16), one can derive
2B(n) = nblg nc − 2blg nc+1 + 2n − F (n) =
[by

Pn

i=1 dlg ie

= nblg nc − 2blg nc+1 + n + 1 from [Knu97]]
=

n
X

dlg ie − 1 + n − F (n) =

i=1

[by (37)]
= W (n) − 1 + n − F (n).
The above yield the following characterization.
Theorem 5.1. For every positive integer n, the difference between twice the
number B(n) of comparison of keys performed in the best case and the number
W (n) of comparison of keys performed in the worst case by MergeSort while
sorting an n-element array is:
2B(n) − W (n) = n − 1 − F (n),
where F (n), visualized on Figure 8, is given by (18).
Proof. Follows from the above discussion.
13

See (A.7) in the Appendix A.

(38)

M. A. Suchenek: Best-case Analysis of MergeSort (MS) v2

19

In particular, since for every positive integer n,
0 ≤ F (n) ≤

n−1
2

(39)

(see Figure 8 for explanation), I conclude with the following tight linear
bounds on 2B(n) − W (n).
Corollary 5.2. For every positive integer n, the difference between twice the
minimum number B(n) and the maximum number W (n) of comparison of
keys performed in the worst case by MergeSort while sorting an n-element
array satisfies this inequality:
n−1
≤ 2B(n) − W (n) ≤ n − 1.
2

(40)

Proof. Follows from (38) and (39).

140
120
100
80
60
40
20

20

40

60

80

100

120

140

Figure 12: A graph of 2B(n) − W (n) shown between graphs of its tight linear bounds
n − 1 and n−1
2 .

Obviously, 2B(n) − W (n) = n − 1 whenever F (n) = 0, that is, whenever
n = 2blg nc . It can be shown that 2B(n) − W (n) = n−1
whenever n =
2
1 k+1
k
(2
+
(−1)
)
for
some
integer
k
≥
0.
3
A graph of 2B(n) − W (n) and its tight bounds are shown on Figure 12.

M. A. Suchenek: Best-case Analysis of MergeSort (MS) v2

20

6. The sum of digits problem
A known explicit formula, published in [Tro68], for the total number of
bits in all integers between 0 and n (not including 0 and n) is expressed in
terms of function Zigzag (referred to as 2g in [Tro68]) and is given by:14

Let g(x) be periodic of period 1 and defined on [0, 1] by

It has been shown in [McI74] that the recurrence relation for A(n, 2) is the
same as the recurrence relation for B(n) given by (2) and (3). Therefore, the
formula (13) derived in this paper is equivalent to A(n, 2) given above by the
considerably more complicated definition. Interestingly, the above definition
can be simplified to (13) along the lines of the elementary derivation of the
alternative formula (36) for B(n) on page 1715 .
7. Proof of Theorem 2.2 page 8, Subsection 2.3
In this Section, I provide an analytic proof of the experimentally-derived
Theorem 2.2 page 8, Subsection 2.3 that was instrumental for the derivation
of a logarithmic-length formula16 for B(n). The result and its proof have a
14

The following are screen shots and an excerpt from [Tro68].
Even more interestingly, if someone did bother to simplify Trollope’s formula of [Tro68]
then I am not aware of it.
Pblg nc
n
16
B(n) = n2 (blg nc + 1) − k=0 2k Zigzag ( 2k+1
), where Zigzag (x) = min(x − bxc, dxe −
x).
15

M. A. Suchenek: Best-case Analysis of MergeSort (MS) v2

21

flavor of Concrete Mathematics. Although they are interesting in their own
right, they cannot be found in [RGP94].
Theorem 7.1. (Same as Theorem 2.2.) For every natural number n and
every positive natural number m,
2m−1
X

m−1

X n+i
n+i
n
b
c−
b
c = 2m × Zigzag (
),
2m
2m
2m
i=m
i=0

(41)

where Zigzag is a function defined by (7) and visualized on Figure 5 page 8.
Proof. First, let’s note that
m−1
m−1
m−1
X n + i + m m−1
X n+i
X n+i 1
n+i
n+i X n+i
c−
b
c=
b
c−
b
c=
(b
+ c−b
c),
b
2m
2m
2m
2m
2m 2
2m
i=0
i=0
i=0
i=0
i=m

2m−1
X

that is,
2m−1
X

b

i=m

m−1
m−1
X n+i
X n+i 1
n+i
n+i
c−
b
c=
(b
+ c−b
c).
2m
2m
2m
2
2m
i=0
i=0

(42)

Let
n = k × 2m + r,

(43)

where 0 ≤ r < 2m, and let 0 ≤ i < m. We have
b

k × 2m + r + i 1
r+i 1
n+i 1
+ c=b
+ c=k+b
+ c
2m
2
2m
2
2m
2

and

n+i
k × 2m + r + i
r+i
c=b
c=k+b
c.
2m
2m
2m
Thus, by virtue of (42),
b

2m−1
X

m−1
m−1
X n+i
X r+i 1
n+i
r+i
b
c−
b
c=
(b
+ c−b
c).
2m
2m
2m
2
2m
i=m
i=0
i=0

We have


 1 if

r+i 1
r+i
b
+ c−b
c=

2m
2
2m

1
2

≤

r+i
2m

0 otherwise,

(44)

<1
(45)

M. A. Suchenek: Best-case Analysis of MergeSort (MS) v2
because r+i
+ 21 <
2m
r+i
1
c − b 2m c ≤ 1.
2

3m
2m

+

1
2

22

= 2 so that b r+i
+ 12 c ≤ 1 and, therefore, b r+i
+
2m
2m

Let I be defined as
I = {i ∈ N |

1
r+i
≤
< 1} = {i ∈ N | m − r ≤ i < 2m − r}.
2
2m

(46)

By virtue of (45), we have
m−1
X
i=0

(b

X r+i 1
X
r+i 1
r+i
r+i
+ c−b
c) =
(b
+ c−b
c) =
1 = #I, (47)
2m 2
2m
2m 2
2m
i∈I
i∈I

where #(I) denotes the cardinality of I.
If r ≤ m then, by (46), #I = m − (m − r) = r. If r > m then, by (46),
#I = 2m − r. In any case,
#I = min(r, 2m − r) = 2m min(
[since 0 ≤

r
2m

r
r
,1 −
)=
2m
2m

< 1 so that b r+i
c = 0 and d r+i
e = 1]
2m
2m
= 2m min(

r
r
r
r
−b
c, d
e−
)=
2m
2m
2m
2m

[by the definition (7) of function Zigzag]
= 2m × Zigzag (

r
)=
2m

[since Zigzag is a periodic function with period 1]
= 2m × Zigzag (k +

r
k × 2m + r
) = 2m × Zigzag (
)=
2m
2m

[by (43)]
= 2m × Zigzag (

n
).
2m

Thus

n
).
2m
From (42), (44), (47), and (48), I conclude (41).
#I = 2m × Zigzag (

(48)

M. A. Suchenek: Best-case Analysis of MergeSort (MS) v2

23

8. Proof of Theorem 3.1 page 15, Section 3
In this Section, I present a brief discussion/motivation of what can be
generally considered a closed-form formula for a function from the set of
real numbers into a set of real numbers. I provide an analytic proof of
Theorem 3.1 page 15, Section 3 that implies the non-existence of closed-form
formula for the minimum number B(n) of comparisons of keys by MergeSort
while sorting an n-element array. I am going to use the acronym cff as an
abbreviation for closed-form formula.
For reader’s convenience, the Theorem 3.1 is quoted below as Theorem 8.1.
Theorem 8.1. (Same as Theorem 3.1.) There is no cff ϕ(n) the values of
Pblg nc
n
), for all positive integers n, that is,
which coincide with k=0 2k Zigzag ( 2k+1
for every cff ϕ(n) on function Zigzag there is a positive n such that
blg nc

X

2k Zigzag (

k=0

n
2k+1

) 6= ϕ(n),

(49)

where Zigzag is a function defined by (7) and visualized on Figure 5.
The rest of this Section constitutes the proof of Theorem 8.1.
First, let me use an example of function 2x : R −→ R as an insight of
what may be accepted as a cff for a continuous function - like, say, F̃ (x) on the set R of reals or on an interval thereof. One picks a dense17 subset Q
of R, with a collection of mappings ρx (i) : N −→ Q, where x ∈ R, given by
so that limi→∞ ρx (i) = x. Since for any x ∈ R \ Q, 2x has been
ρx (i) = bi×xc
i
defined as
√
i
(50)
2x = lim 2ρx (i) = lim 2bi×xc ,
i→∞
i→∞
√
i
limi→∞ 2bi×xc is considered a cff α : R −→ R for 2x .
Lemma 8.2. For every positive integer n,
F̃ (
17

n

)=
2blg nc

In the metric topology of R.

n(blg nc + 2) − 2B(n)
− 2,
2blg nc

(51)

M. A. Suchenek: Best-case Analysis of MergeSort (MS) v2

24

0.7
0.6
0.5
0.4
0.3
0.2
0.1
-0.2

0.2

0.4

0.6

0.8

Figure 13: A graph of the Blancmange function F̃ (x) =

1.0

1.2

P∞

1
i
i=0 2i Zigzag(2 x).

where the function F has been defined by the equality (16) page 11, the function F̃ , visualized on Figure 13 18 , has been defined by the equality (26)
page 14, and the function B(n) has been defined by the equations (2) and (4)
page 6.
Proof. From (16) page 11, I compute
blg nc

X

2i+1 Zigzag (

i=0

n
2i+1

) = F (n) + 2blg nc+1 − n,

that is,
blg nc

X

2i Zigzag (

i=0

1
n
blg nc
)
=
F
(n)
+
2
−
.
2i+1
2
2
n

Applying (52) to the equality (14) page 10, I conclude
B(n) =

n
1
n
(blg nc + 1) − ( F (n) + 2blg nc − ),
2
2
2

or
B(n) =

n
1
n
(blg nc + 1) − F (n) − 2blg nc + ,
2
2
2

that is,
1
n
n
F (n) = (blg nc + 1) − B(n) − 2blg nc + ,
2
2
2
18

Also, together with its partial sums, on Figure 10, page 14.

(52)

M. A. Suchenek: Best-case Analysis of MergeSort (MS) v2

25

or
F (n) = n(blg nc + 2) − 2B(n) − 2blg nc+1 .

(53)

On the other hand, by virtue of (18) page 12,
blg nc

X

F (n) =

i=1

n
2i Zigzag ( i ) =
2

[putting j = blg nc − i]
blg nc−1

=

X

blg nc−j

2

Zigzag (

j=0

[since for j ≥ blg nc,

2j n
2blg nc

n
2blg nc−j

blg nc−1
blg nc

)=2

X
j=0

1
2j n
Zigzag ( blg nc ) =
2j
2

j

2 n
∈ N so that Zigzag ( 2blg
nc ) = 0]

blg nc

=2

∞
X
2j n
1
Zigzag
(
)=
2j
2blg nc
j=0

[by (26) page 14]
2blg nc F̃ (

n
2blg nc

Thus,
F (n) = 2blg nc F̃ (
or

).
n

2blg nc

)

1
)
=
F (n).
2blg nc
2blg nc
Combining equalities (53) and (55) yields
F̃ (

F̃ (

n
2blg nc

)=

1
2blg nc

n

(54)
(55)

(n(blg nc + 2) − 2B(n) − 2blg nc+1 ),

or (51).
Lemma 8.3. If the function B(n) defined by the equations (2) and (4) has a
cff β : N −→ N then the function F̃ (x) defined by the equation (26) page 14
has a cff ϕ : [1, 2) −→ [0, 32 ].

M. A. Suchenek: Best-case Analysis of MergeSort (MS) v2
Proof. Let
D={

n
2blg nc

26

| n ∈ N}

(56)

be the set of rationals in the interval [1, 2) with finite binary expansions19 ,
enumerated by ν(n) : N −→ D given by ν(n) = 2blgn nc and visualized on
Figure 14.
2.0

1.8

1.6

1.4

1.2

1.0
0

500

1000

Figure 14: A graph of enumeration ν(n) =

1500
n
2blg nc

2000

of the set D.

D is a dense subset of the interval [1, 2) of reals. Indeed, if x ∈ [1, 2) then
n
for every n ∈ N, b22nxc ∈ D and
b2n xc
lim
= x.
n→∞ 2n

(57)

Hence, for any x ∈ [1, 2), putting
n = b2i xc,

(58)

so that
blg nc = blgb2i xcc = blg 2i xc = bi + lg xc = i + blg xc = i
19

It is a trivial exercise to show that every real number with finite binary expansion in
the interval [1, 2) is of the form 2blgn nc for some n ∈ N, and it is obvious that every real
number of that form has a finite binary expansion and falls into that interval.

M. A. Suchenek: Best-case Analysis of MergeSort (MS) v2

27

[the last equality holds because 1 ≤ x < 2 so that 0 ≤ lg x < 1 and blg xc =
0], or
blg nc = i,
(59)
we conclude, by virtue of (57),
b2i xc
)=
i→∞ 2i

F̃ (x) = F̃ ( lim
[by the continuity of F̃ (x)]
= lim F̃ (
i→∞

b2i xc
)=
2i

[by the equality (51) of Lemma 8.2]
b2i xc
b2i xc(i + 2) − 2B(b2i xc)
ib2i xc − 2B(b2i xc)
−2
=
lim
+
lim
2
−2 =
i→∞
i→∞
i→∞
2i
2i
2i

= lim

[by the equality (57)]
ib2i xc − 2B(b2i xc)
+ 2x − 2.
i→∞
2i
lim

Thus, for any x ∈ [1, 2),
ib2i xc − 2B(b2i xc)
+ 2x − 2.
i→∞
2i

F̃ (x) = lim

(60)

The equality (60) shows that if there is a cff β : N −→ N for function B
defined by the equations (2) and (4) page 6 then there is a cff ϕ : [1, 2) −→
[0, 23 ] given by
ib2i xc − 2β(b2i xc)
lim
+ 2x − 2
i→∞
2i
for F̃ (x). This completes the proof of Lemma 8.3.
Should the nowhere-differentiable function F̃ have a cff , it would be differentiable everywhere except, perhaps, on a non-dense subset of R. The
following inductive argument demonstrates that. All atomic cff s are differentiable except, perhaps, on a non-dense subset of R. If a finite number of
cff s are differentiable except, perhaps, on non-dense subsets of R then their

M. A. Suchenek: Best-case Analysis of MergeSort (MS) v2

28

composition is differentiable except, perhaps, on non-dense subsets of R.
Thus F̃ has no cff .

20

The above observation, together with Lemma 8.3, complete the proof of
Theorem 8.1.
9. Proof of Theorem 4.1 page 17, Section 4
In this Section, I provide an analytic proof of experimentally-derived Theorem 4.1 page 17, Section 4. This result, re-stated by Theorem 9.1 below,
allows for practically efficient computations of values of the continuous Blackmange function for reals with finite binary floating-point representations. I
also provide some properties (Lammas 9.2, 9.3, and 9.4) of the Zigzag function, given by the equality (7) page 8 and visualized on Figure 5 page 8, that
are useful for a neat derivation of a formula for the Blancmange function as
(the limit of) a finite sum of some values of the Zigzag function.
Let the function21 F̃ , visualized on Figure 13 page 24, be defined by (26)
page 14, and B(n), given by (2) and (4) page 6, be the least number of
comparisons of keys that MergeSort performs while sorting an n-element
array.
Theorem 9.1. (Same as Theorem 4.1.) For every positive integer n
integer k with n ≤ 2k ,
F̃ (

n × k − 2B(n)
n
)
=
.
2k
2k

22

and

(61)

The reminder of this Section constitutes a proof of Theorem 9.1.
Note. Function Zigzag, visualized on Figure 5 page 8, has been defined
by (7) page 8.
Lemma 9.2. For every k ≥ blg nc + 2,
2k Zigzag(

n
) = n.
2k

(62)

√
For instance, function xZigzag( x1 ) is differentiable on [0, 1], except for the non-dense
set {0} ∪ { n1 | n ∈ N}.
21
Known as the Blancmange function.
22
Of course, one if free to assume that n is odd here.
20

M. A. Suchenek: Best-case Analysis of MergeSort (MS) v2

29

Proof. Let k ≥ blg nc + 2, or 2k ≥ 2 × 2blg nc+1 > 2n, that is
2k > 2n.
We have:
0≤b

(63)

n
c≤
2k

[by (63)]
≤b

1
n
c=b c=0
2n
2

or
b

n
c = 0.
2k

Also,
1≤d

(64)

n
e≤
2k

[by (63)]
≤d

n
1
e=d e=1
2n
2

or
d

n
e = 1.
2k

Now,
2k Zigzag(

(65)

n
)=
2k

[by (7) page 8]
= 2k min{

n
n
n
n
n
n
− b k c, d k e − k } = min{n − 2k b k c, 2k d k e − n} =
k
2
2
2
2
2
2

[by (64) and (65)]
= min{n, 2k − n} =
[since by (63), 2k − n ≥ n]
= n.
Hence, (62) holds.
Lemma 9.3. For every k ≥ blg nc + 1,
k
X
i=blg nc+2

n
2i Zigzag( i ) = n × k − n(blg nc + 1).
2

(66)

M. A. Suchenek: Best-case Analysis of MergeSort (MS) v2

30

Proof. By induction on k.
Basis step: k = blg nc + 1.
blg nc+1

X

L=

i=blg nc+2

n
2i Zigzag( i ) = 0.
2

R = n(blg nc + 1) − n(blg nc + 1) = 0.
Hence, L = R. This completes the Basis step.
Inductive step: k ≥ blg nc + 2.
Inductive hypothesis: (66).

k+1
X
i=blg nc+2

n
2i Zigzag( i ) =
2

k
X
i=blg nc+2

n
n
2i Zigzag( i ) + 2k Zigzag( k ) =
2
2

[by the Inductive hypothesis and by the equality (62) of Lemma 9.2]
= n × k − n(blg nc + 1) + n = n × (k + 1) − n(blg nc + 1).
Thus

k+1
X
i=blg nc+2

n
2i Zigzag( i ) = n × (k + 1) − n(blg nc + 1).
2

This completes the Inductive step.
Lemma 9.4. For every k ≥ blg nc + 1,
k

X
n
n
2 F̃ ( k ) =
2i Zigzag( i ).
2
2
i=1
k

Proof. By the definition (26) page 14 of function F̃ , we get:
∞

X 1
n
n
2 F̃ ( k ) = 2k
Zigzag(2i k ) =
i
2
2
2
i=0
k

(67)

M. A. Suchenek: Best-case Analysis of MergeSort (MS) v2

31

[since for every integer x, Zigzag(x) = 0, so that for i ≥ k, Zigzag(2i 2nk ) = 0]
= 2k

k−1
k−1
X
X
1
n
i n
Zigzag(2
)
=
2k−i Zigzag( k−i ) =
i
k
2
2
2
i=0
i=0

[putting j = k − i]
=

k
X

2j Zigzag(

j=1

n
),
2j

which completes the proof of (67).
At this point, we are ready to conclude the proof of Theorem 4.1.
By virtue of (14) page 10, we have:
blg nc

2B(n) = n(blg nc + 1) −

X

2k+1 Zigzag(

k=0
blg nc+1

= n(blg nc + 1) −

X
i=1

= n(blg nc + 1) −

k
X
i=1

n
2k+1

)=

n
2i Zigzag( i ) =
2

n
2 Zigzag( i ) +
2

k
X

i

i=blg nc+2

n
2i Zigzag( i ) =
2

[by Lemmas 9.3 and 9.4]
= n(blg nc + 1) − 2k F̃ (

n
n
) + n × k − n(blg nc + 1) = n × k − 2k F̃ ( k ),
k
2
2

that is,
2B(n) = n × k − 2k F̃ (

n
),
2k

from which (62) follows.
This completes the proof of Theorem 4.1.
Note. A glance at the proof of Lemma 9.3 suffices to notice that it fails if
n > 2k , and so does Theorem 4.1. In particular, for k = blg nc, Lemma 8.2
page 23 yields
n
n × k − 2B(n) 2n
n × k − 2B(n)
)=
+ k −2>
k
k
2
2
2
2k
2n
since for n > 2blg nc , 2blg
nc − 2 > 0.
F̃ (

(68)

M. A. Suchenek: Best-case Analysis of MergeSort (MS) v2

32

References
[Baa91] Sara Baase. Computer Algorithms: Introduction to Design and
Analysis. Addison-Wesley Publishing, 2nd edition, 1991.
[Knu97] Donald E. Knuth. The Art of Computer Programming, volume 3.
Addison-Wesley Publishing, 2nd edition, 1997.
[McI74] M. D. McIlroy. The number of 1’s in binary integers: Bounds and
extremal properties. SIAM Journal of Computing, 3(4):255–261,
December 1974.
[RGP94] Donald Knuth Ronald Graham and Oren Patashnik.
Concrete Mathematics: A Foundation for Computer Science. Addison–Wesley, 1994.
[SF13] Robert Sedgewick and Philippe Flajolet. An Introduction to the
Analysis of Algorithms. Pearson, 2013.
[Suc16] Marek A. Suchenek.
Best-case analysis of MergeSort
with an application to the sum of digits problem (MS).
https://arxiv.org/pdf/1607.04604v1, July 18 2016.
[Tro68] J. R. Trollope. An explicit expression for binary digital sums. Mathematics Magazine, 41(1):21–25, Jan.–Feb. 1968.

APPENDIX
Appendix A. P
A derivation of the worst-case running time W (n) =
n
i=1 dlg ie of MergeSort
Let’s assume that n ≥ 2 is large enough to spur a cascade of many
recursive calls to MergeSort following the recursion tree T , a sketch of which
is shown on Figure 2.
The nodes in tree T correspond to calls to MergeSort and show sizes
of (sub)arrays passed to those calls. The root corresponds to the original
call to MergeSort. If a call that is represented by a node p executes further

M. A. Suchenek: Best-case Analysis of MergeSort (MS) v2

33

recursive calls to MergeSort then these calls are represented by the children
of p; otherwise p is a leaf. Thus, T is a 2-tree23 .
The levels in tree T are enumerated from 0 to h, where h is the number
of the last level of the tree, or - in other words - the depth of T . On Figure 2,
they are shown on the left side of the tree. The root is at the level 0, its
children are at level 1, its grand children are at level 2, its great grand children
(not shown on the sketch) are at level 3, at so on. Clearly, since every call
to MergeSort on a sub-array of size ≥ 2 executes two further recursive calls
to MergeSort, only the nodes that show value 1 are leaves and all other
nodes have 2 children each. Thus, since all nodes in the last level h are
leaves, they all show value 1. And since the original input array gets split,
eventually, onto n 1-element sub-arrays, the number of all leaves in T is n.
(This, however, does not mean that the last level h necessarily contains all
the leaves of T .)
If a level i has 2i nodes, each of them showing a value ≥ 2, then each
such node has 2 children so that level i + 1 has twice the number of nodes in
level i, that is, 2i+1 nodes. Since level 0 has 20 nodes, it follows (completion
of a proof by induction with the basis and inductive steps outlined above is
left as an exercise for the reader) that if k is the level number of any level
above which all the nodes show values ≥ 2 then all levels i = 0, ...k contain
exactly 2i nodes each.
The last level h may contain 2h nodes or less. We are going to show
that each level i above level h contains exactly 2i nodes. Here is a very
insightful property that we are going to use for that purpose. It states that
MergeSort is splitting its input array fairly evenly so that at any level of the
recursive tree, the difference between the lengths of the longest sub-array and
the shortest sub-array is ≤ 1. This fact is the root cause of good worst-case
performance of MergeSort.
Property Appendix A.0.1. The difference between values shown by any
two nodes in the same level of the recursion tree for MergeSort is ≤ 1.
Proof. The Property clearly holds for level 0. We will show that if it holds
for level i and i is not the last level of the recursion tree (that is, i < h) then
it also holds for the level i + 1.
23

A binary tree whose every non-leaf has exactly 2 children.

M. A. Suchenek: Best-case Analysis of MergeSort (MS) v2

34

Let us assume that the Property holds for some level i < h. Let c ≤ d be
numbers shown by any two (not necessarily distinct) nodes in level i + 1. It
suffices to show that
d − c ≤ 1.
(A.1)
Let a ≤ b be the numbers shown by the parents of the mentioned above
nodes. Those parents, of course, must reside in the level i. By the inductive
hypothesis (that holds for level i), b − a ≤ 1, that is,
a ≤ b ≤ a + 1.

(A.2)

The numbers shown by all their four children are b a2 c, d a2 e, b 2b c and d 2b e,
respectively, so the largest difference between any of those four numbers is
d 2b e − b a2 c. In particular, d − c is not larger than that. We have:
b
a
d−c≤d e−b c≤
2
2
[by (A.2)]
a
a+1
e−b c
2
2
c
c+1
[since for any integer c, d 2 e = b 2 c]
≤d

=b

a+2
a
a
a
c − b c = b + 1c − b c =
2
2
2
2

[since for every x, bx + 1c = bxc + 1]
a
a
= b c + 1 − b c = 1.
2
2
Thus (A.1) holds. This completes the inductive step and completes the proof
of the Property.
As we have noted, the values shown at all nodes in the last level h are all
1. Thus the values shown at their parents, that reside at level h − 1 are all 2,
and the values shown at their grand parents, that reside at level h − 2 are all
≥ 3. Thus, by Property Appendix A.0.1, all nodes at level h − 2 show values
≥ 2, and, therefore (as we have proved before), all levels i = 0, ..., h − 1 have
2i nodes, each, as it has been visualized on Figure 2.

M. A. Suchenek: Best-case Analysis of MergeSort (MS) v2

35

Theorem Appendix A.0.2. The depth h of the recursion tree T (n) for
MergeSort run on an array of size n is
h = dlg ne.

(A.3)

Proof. Since every level of T , except, perhaps, for the last level, has the
maximal number of nodes, a 2-tree with n leaves could not be any shorter
than T . So, T is a shortest 2-tree with n leaves. Therefore (by a well known
fact), its depth h is equal to dlg ne. Thus (A.3) holds.
Because each node in any level above h − 1 shows value ≥ 2, it has 2
children. Thus the value it shows is equal to the sum of values shown by its
children, as we have indicated at the beginning of this section. From that
we conclude (a proof by induction is left as an exercise for the reader) that
the sum of values shown at nodes in any level i = 0, ..., h − 1 is the same for
each such level. Thus the said sum is equal to the value showed by the only
node at level 0, that is, is equal to n.
Let a1 , ..., a2i be the values shown at the nodes of some level i = 0, ..., h−1.
The number of comps performed by a call to Merge invoked by the call to
MergeSort on an array of aj elements is either 0 if aj = 1 (no call to Merge
is made) or, as we have shown in the previous section, is aj − 1 if aj ≥ 2. So,
in either case, it is aj − 1. Thus the number of comps Ci performed at level
i is
Ci = (a1 − 1) + ... + (a2i − 1) = (a1 + ... + a2i ) − (1 + ... + 1) = n − 2i . (A.4)
|
{z
}
2i

Moreover, since all nodes at the last level h are 1’s
Ch = 0.

(A.5)

Therefore, the total number W (n) of comps that MergeSort performs in the
worst case on an n-element array is equal to
W (n) =

h
X

Ci =

i=0

[by (A.5)]
=

h−1
X
i=0

Ci =

M. A. Suchenek: Best-case Analysis of MergeSort (MS) v2

36

[by (A.4)]
h−1
X
=
(n − 2i ) = nh − (2h − 1) = nh − 2h + 1 =
i=0

[by (A.3)]
= ndlg ne − 2dlg ne + 1.
This way I have proved the following.
Theorem Appendix A.1. The number W (n) of comparisons of keys that
MergeSort performs in the worst case while sorting an n-element array is
W (n) = ndlg ne − 2dlg ne + 1.

(A.6)


Proof follows from the above derivation.
Using the well-known24 closed-form formula for
that
n
X
W (n) =
dlg ie.

Pn

i=1 dlg ie,

I conclude
(A.7)

i=1

Appendix B. Proof of

Pm−1
i=0

b n+i
c=n
m

Theorem Appendix B.0.3. For every natural number n and every positive
natural number m,
m−1
X n+i
c = n.
b
m
i=0
Proof. Let n = km + l, where 0 ≤ l < m.
We have
km + l + i
l+i
l+i
n+i
c=b
c = bk +
c=k+b
c.
m
m
m
m
Therefore,
b

m−1
X

m−1
m−1
m−1
X l+i
X l+i
X
n+i
b
c = mk+
b
c = mk+
b
c = mk+
1 = mk+l = n.
m
m
m
i=0
i=0
i=m−l
i=m−l

24

See [Knu97].

M. A. Suchenek: Best-case Analysis of MergeSort (MS) v2

37

References
[Baa91] Sara Baase. Computer Algorithms: Introduction to Design and
Analysis. Addison-Wesley Publishing, 2nd edition, 1991.
[Knu97] Donald E. Knuth. The Art of Computer Programming, volume 3.
Addison-Wesley Publishing, 2nd edition, 1997.
[McI74] M. D. McIlroy. The number of 1’s in binary integers: Bounds and
extremal properties. SIAM Journal of Computing, 3(4):255–261,
December 1974.
[RGP94] Donald Knuth Ronald Graham and Oren Patashnik.
Concrete Mathematics: A Foundation for Computer Science. Addison–Wesley, 1994.
[SF13] Robert Sedgewick and Philippe Flajolet. An Introduction to the
Analysis of Algorithms. Pearson, 2013.
[Suc16] Marek A. Suchenek.
Best-case analysis of MergeSort
with an application to the sum of digits problem (MS).
https://arxiv.org/pdf/1607.04604v1, July 18 2016.
[Tro68] J. R. Trollope. An explicit expression for binary digital sums. Mathematics Magazine, 41(1):21–25, Jan.–Feb. 1968.
c 2016 Marek A. Suchenek. All rights reserved by the author.
A non-exclusive license to distribute this article is granted to arXiv.org.

