Elementary Yet Precise Worst-case Analysis of MergeSort, A short version (SV)
Marek A. Suchenek



theoremTheorem[section]
thm[theorem]Theorem
lem[theorem]Lemma
corollary[theorem]Corollary
cor[theorem]Corollary
df[theorem]Definition
ex[theorem]Example
mth[theorem]The Main Theorem
linthm[theorem]Linearity Theorem
defthm[theorem]Definability Theorem
mapth[theorem]The Mapping Theorem
mlm[theorem]The Main Lemma
remlm[theorem]The RemoveMax Invertibility Lemma
racrlm[theorem]The RemoveAll Cost Lemma
rmcrlm[theorem]The RemoveMax Cost Lemma
losslm[theorem]Credit Loss Characterization Lemma
pqlm[theorem]The pq Lemma
fixlm[theorem]Subheap Repair Lemma
unlm[theorem]The Uniqueness Lemma
complem[theorem]Competition Lemma
diaglem[theorem]Diagram Lemma
fundlem[theorem]Fundamental Lemma
charlem[theorem]Worst-case Heap Characterization Lemma
sLBlm[theorem]∑λ Lower Bound Lemma
dth[theorem]Decomposition Theorem
sith[theorem]Singularity Theorem
1LBth[theorem]The 1^ Lower Bound Theorem
2LBth[theorem]The Lower Bound Theorem
UBth[theorem]The Upper Bound Theorem
1oth[theorem]The 1^st Optimality Theorem
2oth[theorem]The 2^nd Optimality Theorem
3oth[theorem]The 3^rd Optimality Theorem
cropt[theorem]Optimality Criterion
hyp[theorem]Hypothesis
example[theorem]Example
property[theorem]Property
note[theorem]Note
algMergeSort[theorem]Algorithm MergeSort
exercise[theorem]Exercise

theorem1Theorem[subsection]
thm1[theorem1]Theorem
lemma1[theorem1]Lemma
claim1[theorem1]Claim
corollary1[theorem1]Corollary
df1[theorem1]Definition
proposition1[theorem1]Proposition
problem1[theorem1]Problem
example1Example[subsection]
conjecture1[theorem1]Conjecture
remark1[theorem1]Remark
property1[theorem1]Property
algMergeSort1[theorem1]Algorithm MergeSort
linthm1[theorem1]Linearity Theorem
defthm1[theorem1]Definability Theorem


myheadings
M.A.SuchenekSuchenek:  Elementary Yet Precise Worst-case Analysis of MergeSort (SV)





[label1]2017 Marek A. Suchenek.


California State University Dominguez Hills,
Department of Computer Science, 

1000 E. Victoria St., Carson, CA 90747, USA,
  


The full version of this paper offers two elementary yet precise derivations of an exact formula 
 
    W(n) = ∑_i=1 ^n⌈ i ⌉ = n ⌈ n ⌉ - 2^⌈ n ⌉ + 1

for the maximum number W(n) of comparisons of keys performed by MergeSort on an n-element array. The first of the two, due to its structural regularity, is well worth carefully studying in its own right. 



Close smooth bounds on W(n) are derived. It seems interesting that W(n) is linear between the points n = 2^⌊ n ⌋ and it linearly interpolates its own lower bound n  n - n + 1 between these points.



The manuscript (MS) of the full version of this paper, dated January 20, 2017, can be found at: 













 MergeSort sorting worst case.


[2010] 68W40    	Analysis of algorithms 


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


ACM classes: 	F.2.2; G.2.0; G.2.1; G.2.2









 



§ INTRODUCTION


MergeSort is one of the fundamental sorting algorithms that is being taught in undergraduate Computer Science curricula across the U.S. and elsewhere. Its worst-case performance, measured by the number of comparisons of keys performed while sorting them, is optimal for the class of algorithms that sort inductively[Inductive sorting of n keys sorts a set of n-1 of those keys first, and then “sorts-in” the remaining n-th key.] by comparisons of keys.[In its standard form analyzed in this paper, MergeSort is not an inductive sorting algorithm. However, its worst-case performance, measured by the number of comparisons of keys performed while sorting them, is equal to the worst-case performance of the binary insertion sort first described by Steinhaus in <cit.> that is worst-case optimal in the class of inductive sorting algorithms that sort by comparisons of keys; see <cit.> page 186.] Historically, it[A bottom-up version of it, invented by John Neumann.] was the first sorting algorithm to run in O(n  n) time[In the worst case.].



So it seems only fitting to provide an exact formula for MergeSort's worst-case performance and derive it precisely.
Unfortunately, many otherwise decent texts offer  unnecessarily imprecise[Notable exceptions in this category are <cit.> and <cit.> that derive almost exact formulas, but see Section <ref> page sec:oth for a brief critique of the results and their proofs offered there.] variants of it, and some with quite convoluted, incomplete, or incorrect proofs. Due to these imperfections, the fact that the worst-case performance of MergeSort
is the same as that of another benchmark sorting algorithm, the  binary insertion sort  of <cit.>, has remained unnoticed[Even in <cit.>.].




In this paper, I present two outlines[The detailed derivations can be found in <cit.>.] of elementary yet precise and complete derivations of an exact formula
 
    W(n) = ∑_i=1 ^n⌈ i ⌉ = n ⌈ n ⌉ - 2^⌈ n ⌉ + 1

for the maximum number W(n) [Elementary derivation of an exact formula for the best-case performance B(n) of MergeSort, measured by the number of comparisons of keys performed while sorting them, has been done in <cit.>; see Section <ref> page sec:best of this paper.] of comparisons of keys performed by MergeSort on an n-element array. The first of the two, due to its structural regularity, is well worth carefully studying in its own right. 



Unlike some other basic sorting algorithms[For instance, Heapsort; see <cit.> for a complete analysis of its worst-case behavior.] that run in O(n  n) time, MergeSort exhibits a remarkably regular[As revealed by Theorem <ref>, page thm:mersorbounds.] worst-case behavior, 
the elegant simplicity of which
has been mostly lost on its rough analyses. In particular,
W(n) is linear[See Figure <ref> page fig:boundsMergeSort.] between the points n = 2^⌊ n ⌋ and it linearly interpolates its own lower bound n  n - n + 1 [Given by the left-hand side of the inequality (<ref>) page eq:mersorbounds.] between these points.



What follows is a short version (SV) of a manuscript dated January 20, 2017, of the full version version <cit.> of this paper that has been posted at: 

 

The derivation of the worst case of MergeSort presented here is roughly the same[Except for the present proof of Lemma <ref> which I haven't been using in my class.] as the one I have been doing in my undergraduate Analysis of Algorithms class. <ref> shows sample class notes from one of my lectures. 






§ SOME MATH PREREQUISITES



A manuscript of the full version <cit.> of this paper contains a clever derivation of a well-known[See <cit.>.] closed-form formula for
∑_i=1 ^n⌈ i ⌉. It proves insightful in my worst-case analysis of MergeSort as its right-hand side will occur on page eq:result in the fundamental equality (<ref>) and serve as an instrument to derive the respective exact formula for MergeSort's worst-case behavior.

 
For every integer n≥ 1,

    ∑_i=1 ^n⌈ i ⌉ = ∑ _y=0^⌈ n ⌉-1 ( n - 2^y) .


Proof in <cit.>.





From this one can easily conclude that:


 
For every integer n≥ 1,

    ∑_i=1 ^n⌈ i ⌉ = n ⌈ n ⌉ - 2^⌈ n ⌉ + 1 .








§ MERGESORT AND ITS WORST-CASE BEHAVIOR W(N)
 


A call to MergeSort inherits an n-element array A of integers and sorts it non-decreasingly, following the steps described below.

 
To 
sort an n-element array A do:



  *  If n ≤ 1 then return A to the caller,

  *  If n ≥ 2 then


  *  pass the first ⌊n/2⌋ elements of A to a recursive call to MergeSort,

  * pass the last ⌈n/2⌉ elements of A to another recursive call to MergeSort,

  *  linearly merge, by means of a call to Merge, the non-decreasingly sorted arrays that were returned from those calls onto one non-decreasingly sorted array  A^',

  *  return A^' to the caller.
   





A Java code of 
Merge is shown on the Figure <ref>.[A Java code of 
MergeSort is shown in <ref> Figure <ref> page fig:Sort.]





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. 


The worst-case running time 

    W(n)

of MergeSort is defined as the maximum number of comps it performs while sorting an array of n distinct[This assumption is superfluous for the purpose of worst-case analysis as the mere presence of duplicates does not force MergeSort to perform more comps.] elements. 


Clearly, if n=0 then W(n) = 0. From this point on, I am going to assume that n ≥ 1.[This assumption turns out handy while using expression n.]




Since no comps are performed outside Merge, W(n) can be computed as the sum of numbers of comps performed by all calls to Merge during the execution of  MergeSort. The following classic results will be useful in my analysis.


 
The maximum number of comps performed by Merge on two sorted list of total number n of elements is n-1.

Proof (constructive, with Java code that generates worst cases shown in the <ref>) in <cit.>.




 Moreover, if the difference between the lengths of merged list is not larger than 1 then no algorithm that merges sorted lists by means of comps beats Merge in the worst case, that is, has a lower than n-1 maximum number of comps.[Proof in <cit.>, Sec. 5.3.2 page 198; the worst-case optimality of Merge (n-1 comps) was generalized in <cit.> over lists of lengths k and m, with k ≤ m, that satisfy 3k ≥ 2m-2.]  This fact makes MergeSort optimal in the intersection of the class of sorting algorithms that sort by merging two sorted lists of lengths' difference not larger than 1 [Or, by virtue of the above-quoted result from <cit.>, with the difference not larger than the half of the length of the shorter list plus 1.]
with the class of sorting algorithms that sort by comps.



§ AN EASY YET PRECISE DERIVATION OF W(N)
 

MergeSort  is a recursive algorithm. If n ≥ 2 then it spurs a cascade of two or more recursive calls to itself.  A rudimentary analysis of the respective recursion tree T_n, shown on Figure <ref>, yields a neat derivation of the exact formula for the maximum number W(n) of comps that MergeSort performs on an n-element array.










The idea behind the derivation
is strikingly simple. It is based on the observation[Which I  prove in <cit.> as Theorem 4.6, page 14.] that for every  k ∈ℕ, the maximum number C_k of comps performed at each level[Empty or not.] k  of T_n is given by this neat formula:[It is a simplification of formulas used in derivation presented in <cit.> and discussed in Section <ref> page sec:oth; in particular, it does not refer to the depth h of the decision tree T_n.]

    C_k = max{n - 2^k, 0} .

Since  

    n - 2^k > 0 ⌈ n ⌉ - 1 ≥ k ,

the Corollary <ref> will allow me to conclude from (<ref>) and (<ref>) the main result of this paper[This is how I have been deriving it in my undergraduate Analysis of Algorithms class for some 15 years or so, now.]:

    W(n)  = ∑ 
    _k ∈ℕ
     C_k = ∑ _k=0^⌈ n ⌉-1 (n - 2^k) = n⌈ n ⌉ - 2^⌈ n ⌉ + 1 = ∑_i=1 ^n⌈ i ⌉.







The missing details[Which I did not show in my Analysis of Algorithms class.] in the above sketch are in <cit.>. Naturally, their only purpose is to prove the equality (<ref>) for all  k ∈ℕ,
as the rest, shown in (<ref>), easily follows from it. 
In particular, we get:


 
The number W(n) of comparisons of keys that MergeSort performs in the worst case while sorting an n-element array is

    W(n) = ∑_i=1 ^n⌈ i ⌉ = n ⌈ n ⌉ - 2^⌈ n ⌉ + 1 .


Proof in <cit.>.







From that we can conclude a usual rough characterization of W(n): 

    W(n) ≤ n ( n + 1) - 2^ n  + 1  =  n  n + n - n + 1 = n  n  + 1

and

    W(n) ≥ n  n  - 2^ n + 1  + 1  =  n  n - 2n + 1.

Therefore,

    W(n) ∈Θ (n log n).






The occurrence of ∑_i=1 ^n⌈ i ⌉ in (<ref>) allows to conclude that W(n) is exactly equal[<cit.> contains no mention of that fact.] to the number of comparisons of keys that the binary insertion sort, considered by H. Steinhaus in <cit.> and analyzed in <cit.>, performs in the worst case. Since the binary insertion sort is known to be worst-case optimal[With respect to the number of comparisons of keys performed.] in the class of algorithms that perform incremental sorting, MergeSort is worst-case optimal in that class[Although it is not a member of that class.], too. From this and from the observation at the end of Section <ref>, page pag:mergopt, I conclude that no algorithm that sorts by merging two sorted lists and only by means of comps is worst-case optimal in the class of algorithms that sort by means of comps as it must perform 8 comps in the worst case while sorting 5 elements[They can be split in two: 1 plus 4, and follow the binary insertion sort, or 2 plus 3, and follow MergeSort.], while one can sort 5 elements by means of comps with no more than 7 comps.  




§ CLOSE SMOOTH BOUNDS ON W(N)



Our formula for W(n) contains a function ceiling that is harder to analyze than arithmetic functions and their inverses. In this Section, I outline a derivation of close lower and upper bounds on W(n) that are expressible by simple arithmetic formulas. I show that these bounds are the closest to W(n) in the class of functions of the form n  n + c n + 1, where c is a real constant.
 
The detailed derivation and missing proofs can be found in <cit.>.



Using the function ε (analyzed briefly in <cit.> and <cit.>), a form of which is shown on Figure <ref>, 
given by:

    ε  = 1 + θ
    - 2^θθ =  ⌈  n ⌉ -    n ,

one can conclude[See <cit.>, Thm. 12.2 p. 94 for a proof.] that, for every n > 0,

    n ⌈ n ⌉ - 2^⌈ n ⌉ = n( n + ε - 1) ,

which yields

    W(n) =  n(  n+ ε - 1) + 1 =  n  n + (ε - 1) n + 1 .




 
Function ε given by (<ref>) is a continuous function of n 
on the set of reals > 0. It assumes the minimum 0 for every  n = 2^⌊ n ⌋ and the maximum 

    δ = 1 -  e +  e ≈ 0.0860713320559342 ,
    [The constant 1 -  e +  e
    has been known as the  Erdös constantδ. Erdös used it around 1955 in order to establish an asymptotic upper bound for the number M(k) of different numbers in a multiplication table of size k × k by means of the following limit:
    
        lim _k →∞lnk × k/M(k)/lnln (k × k) =  δ .
    ]

for every

    n  =  2^⌊ln n +  e ⌋ln 2

and only such n.
The function 
ε restricted to integers never reaches the value δ. However,  δ is the  supremum of ε restricted to integers. 

Proof in <cit.>.


Characterization (<ref>) and Property <ref> yield close smooth bounds of W(n). They are both of the form n  n + c n + 1 and they sandwich tightly W(n) between each other. If one sees W(n) as an infinite polygon[Which it is.], its lower bound circumscribes it and its upper bound inscribes it.

  
W(n) is a continuous concave function, linear between the points n =   2^⌊ n  ⌋, that for every n > 0 satisfies this inequality:


    n  n - n + 1 ≤ W(n) ≤ n  n - (1-δ) n + 1 <  n  n - 0.913 n + 1 ,

with the left ≤ becoming = for every n = 2^⌊ n ⌋ and  the right ≤ becoming = for every n = 2^⌊ n +  e ⌋ln 2, and only for such n. Moreover, the graph of W(n) is tangent to the graph of n  n - (1-δ) n + 1 at the points n = 2^⌊ n +  e ⌋ln 2, and only at such points.

Proof in <cit.>.


	
	
	 The bounds given by (<ref>) are really close[The distance between them is less than δ n ≈ 0.0860713320559342 n for any positive integer n.] to the exact value of W(n), as it is shown on Figure <ref> page fig:boundsMergeSort. The exact value n⌈ n ⌉ - 2^⌈ n ⌉ +1 is a continuous function (if n is interpreted as a real variable) despite that it incorporates discontinuous function ceiling. 
	 
	
	  It seems interesting that W(n) = n⌈ n ⌉ - 2^⌈ n ⌉ +1  (whether n is interpreted as a real variable or an integer variable) is linear between points n = 2^⌊ n ⌋ and linearly interpolates its own lower bound n  n - n + 1 between these points.
	
	
	 
	 For n restricted to positive integers, the inequality (<ref>) can be slightly enhanced by replacing the ≤ symbol with <, with the following result.
 
1-δ is the greatest constant c such that for every integer n ≥ 1, 

    W(n) < n  n - c n + 1.


Proof in <cit.>.




Theorem <ref> can be reformulated as follows.


 

    inf{c ∈ℝ|∀ n ∈ℕ∖{0} , W(n) < n  n - c n + 1 }  = 1 - δ .


Proof in <cit.>.


No upper bound of W(n) that has a form n  n - c n + 1 can coincide with W(n) at any integer n, as the following fact ascertains.

 
There is no constant c such that for every integer n ≥ 1, 

    W(n) ≤ n  n - c n + 1

and for some integer n ≥ 1, 

    W(n) =  n - c n + 1.


Proof in <cit.>.




In particular[Note the ≤ symbol in (<ref>).],

    inf{c ∈ℝ|∀ n ∈ℕ∖{0}, W(n) ≤ n  n - c n + 1 }  = 1 - δ .




Moreover, we can conclude from Theorem <ref> the following fact.

 
1-δ is the greatest constant c such that for every integer n ≥ 1, 

    W(n) ≤⌈ n  n - c n ⌉.


Proof in <cit.>.






Since for any integer n ≥ 1, W(n) is integer, the lower bound given by (<ref>)
yields

    ⌈ n  n ⌉ - n + 1 ≤ W(n) ≤⌈ n  n - 0.913 n ⌉ .

By virtue of Corollary <ref>, for some integers n ≥ 1,[For instance, for n=11.]

    W(n) > ⌈ n  n - 0.914 n ⌉ .

Although the bounds given by (<ref>) [Almost the same bounds were given in <cit.>; see Section <ref> for more details on this.] are tighter than those given by (<ref>), they nevertheless involve the discontinuous ceiling function, so that they may not be as easy to visualize or analyze as some differentiable functions, thus losing their advantage over the precise formula W(n) = n⌈ n ⌉ - 2^⌈ n ⌉ +1. Therefore, the bounds given by (<ref>) appear to have an analytic advantage over those given by (<ref>).




§ OTHER PROPERTIES OF THE RECURSION TREE T_N



This sections contains some well-known auxiliary facts that I didn't need for the derivation of the exact formula for W(n) but am going to derive from the Main Lemma 4.1 of <cit.> for the sake of a thoroughness of my analysis of the decision tree T_n.

 
The depth h of the recursion tree T_n is 

    h = ⌈ n ⌉ .


Proof in <cit.>.




Theorem <ref> allows for quick derivation of fairly close upper bound on the number of comps performed by MergeSort on an n-element array. Since at each level of T_n less than n comparisons are performed by Merge and at level h no comps are performed, and there are h = ⌈ n ⌉ levels below level h, the total number of comps is not larger than

    (n-1)h = (n-1)(⌈ n ⌉) < (n-1) ( n + 1)   ∈ O(n log n).



 






A cut of a tree T_n is a set Γ of nodes of T such that every branch[A maximal path.] in T_n has exactly one element in Γ.

 
The sum of values shown at the elements of any cut of T_n is n.

Proof in <cit.>.





 
The number of leaves in the recursion tree T_n is n.

Proof in <cit.>.


The following corollary provides some statistics about recursive calls to MergeSort.

 
For every integer n > 0,

     
     

  *  T_n has 2n - 1 nodes.


  *  The number or recursive calls spurred by MergeSort on any n-element array is 2(n - 1).


  * 
The sum S_n of all values shown in the recursion tree T_n on Figure <ref> is equal to:

    S_n =  n ⌈ n ⌉ - 2^⌈ n ⌉ + 2n  = n( n + ε + 1).


  * 
The average size A_n of array passed to any recursive call to MergeSort while sorting an n-element array is:

    A_n =  1/2(1+1/n-1) ( n + ε) ≈1/2 ( n + ε).



Proof in <cit.>.





 Here is a very insightful property. It states that MergeSort is splitting its input array fairly evenly[The sizes of the sub-arrays passed to recursive calls at any non-empty level k of the decision tree T_n above the last non-empty level h are the same as the sizes of the elements of the maximally even partition of an n-element set onto 2^k subsets.] 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.

  
The difference between values shown by any two nodes in the same level of of the recursion tree T_n is ≤ 1.
 
Proof in <cit.>.


Property <ref> has this important consequence that Merge is, by virtue of the observation on page pag:mergopt after the Theorem <ref> page thm:merge_n-1, worst-case comparison-optimal while merging any two sub-arrays of the same level of the recursion tree. Thus the worst-case of MergeSort cannot be improved just by replacing Merge with some tricky merging X as long as X merges by means of comparisons of keys.

 
Replacing  Merge with any other method that merges sorted arrays by means of comps will not improve the worst-case performance of MergeSort measured with the number of comps while sorting an array.


Proof follows from the  above observation.





Since a parent must show a larger value than any of its children, the Property <ref> has also the following consequence.
 
The leaves in the recursion tree T_n can only reside at the last two non-empty levels of T_n. 


Proof follows from the Property <ref> as the above observation indicates.


As a result, one can conclude[Cf. <cit.>, Sec. 5.3.1 Ex. 20 page 195.] that the recursion tree T_n has the miminum internal and external path lengths among all binary trees on 2n - 1 nodes.



Since all nodes at the level h of the recursion tree T_n are leaves and show value 1, no node at level h-1 can show a value >2. Indeed, level h-1 may only contain leaves, that show value 1, and parents of nodes of level h that show value 1+1=2. This observation and the previous result allow for easy characterization of contents of the last two non-empty levels of tree T_n.



 
For every n≥ 2: 


     
     

  *  there are 2^h - n leaves, all showing value 1, 
at the level h-1,

  *  there are n - 2^h-1 non-leaves, all showing value 2, 
at the level h-1,
and

  *  there are 2n - 2^h [This value shows in the lower right corner of Figure <ref> page fig:rectre of a sketch of the recursion tree T_n; it was not need needed for the derivation of the main result (<ref>) page eq:levComp2, included for the sake of completeness only.] nodes, all leaves showing value 1, at the level h

of the recursion tree T_n, where h is the depth[The level number of the last non-empty level of T_n.] of T_n.

Proof in <cit.>.




§ A DERIVATION OF W(N) WITHOUT REFERENCES TO THE RECURSION TREE



In order to formally prove Theorem <ref> without any reference to the recursion tree, I use here the well-known[For instance, derived in <cit.> and <cit.>.] recurrence relation

    W(n) = W(⌊n/2⌋) + W(⌈n/2⌉) + n - 1  n ≥ 2


    W(1) = 0

that easily follows from the description (Algorithm <ref> page alg:mersor) of MergeSort, steps <ref>, <ref> and Theorem <ref>. I am going to prove, by direct inspection,  that the function W(n) defined by (<ref>) satisfies equations (<ref>) and (<ref>).



The details of the proof are in <cit.>.



§ OTHER WORK
 

Although some variants of parts of the formula (<ref>) appear to have been known for quite some time now, even otherwise precise texts offer derivations that leave room for improvement. For instance, the recurrence relation for MergeSort analyzed in <cit.> asserts that the least number of comparisons of keys performed outside the recursive calls, if any, that suffice to sort an array of size n is n rather than n-1.  This seemingly inconsequential variation results in a solution W(n) =  ∑_i=1 ^n-1 (⌊ i ⌋ + 2) [I saw W(n) =  ∑_i=1 ^n-1⌊ i ⌋ on slides that accompany <cit.>.] on page 2, Exercise 1.4, rather than the correct formula (<ref>)  W(n) =  ∑_i=1 ^n⌈ i ⌉ derived in this paper. (Also, the relevant derivations presented in  <cit.>, although quite clever, are not nearly as precise and elementary as those presented in this paper.) As a result, the fact that MergeSort performs exactly the same number of comparisons of keys as does another classic, binary insertion sort, considered by H. Steinhaus and analyzed in <cit.>, remains unnoticed.





Pages 176 – 177 of <cit.> contain 
an early sketch of proof of 

    W(n) = n h - 2^h + 1,

where h is the depth of the recursion tree T_n, with remarkably close[Although not 100 percent correct.] bounds given by (<ref>) page eq:baavan_bound. It is similar[The idea behind the sketch of the derivation in <cit.> was based on an observation that 
    W(n) = ∑ _i = 0 ^h-2 (n - 2^i) + n - B/2 ,
 where B was the number of leaves at the level h-1 of the decision tree T_n; it was sketchily derived from the recursion tree shown on Figure <ref> and properties stated in the Corollary <ref> page cor:last2char (with only a sketch of proof in <cit.>)  not needed for the derivation presented in Section <ref>.]  to a simpler 
derivation based on the equality (<ref>), presented in this paper in Section <ref> and outlined in (<ref>) page eq:result (except for the ∑_i=1 ^n⌈ i ⌉ part), which it predates by several years. 







The <cit.>'s version of the decision tree T_n (Figure 4.14 page 177 of <cit.>, shown here on Figure <ref>) was a re-use of a decision tree for the special case of n = 2^⌊ n ⌋, with an ambiguous, if at all correct[It may be interpreted as to imply that for any level k, all the left-child sizes at level k are the same and all the right-child sizes at level k are the same, neither of which is a valid statement.], comment in the caption that “[w]henever a node size parameter is odd, the left child size parameter is rounded up[Should be: down, according to (<ref>) page eq:recmergesort1.] and the right child size is rounded down[Should be: up, according to (<ref>) page eq:recmergesort1.].” The proof of the fact, needed for the derivation in <cit.>, that T_n had no leaves outside its last two levels (Corollary <ref> page cor:last2, not needed for the derivation presented in Section <ref>) was waved with a claim “[w]e can[This I do not doubt.] determine that [...]”




Although h was claimed in <cit.> to be equal to ⌈ (n+1) ⌉ [Which claim must have produced an incorrect formula n ⌈ (n+1) ⌉ - 2^⌈ (n+1) ⌉ + 1 for W(n) and precluded concluding the neat characterization W(n) = ∑_i=1 ^n⌈ i ⌉.] (and not to the correct ⌈ n ⌉ given by the equality (<ref>) page eq:height, a fact not needed for the derivation presented in Section <ref>), somehow the mostly correct conclusion[Almost identical with (<ref>) page eq:mersorbounds2, except for the constant 0.914.]
was inferred from it, however, with no details offered - except for a mention that a function α that satisfies h =  n + α, similar to function ε shown on Figure <ref> page fig:eps, was used. It stated that (Theorem 4.6, page 177, in <cit.>):

    ⌈ n  n - n + 1 ⌉≤ W(n) ≤⌈ n  n - 0.914 n ⌉ .

		
It follows from (<ref>) page eq:wrongbound that the constant 0.914 that appears in (<ref>) is incorrect. It was a rounding error[Of  1 - δ, where δ is given by (<ref>) page eq:Erdos.], I suppose, that produced a false upper bound[For instance, if n = 11 then MergeSort performs 29 comparisons of keys while the value of the upper bound ⌈ n  n - .914 n ⌉ given in <cit.>, Theorem 4.6. p. 177, is 28; this is a significant error as 28 or less comps while sorting any 11-element array beats the binary insertion sort that requires ∑_i=1 ^11⌈ i ⌉ = 29 comps in the worst case.].   



§ BEST-CASE ANALYSIS OF MERGESORT
 

It turns out that derivation of minimum number B(n) of comps performed by MergeSort on an n-element array is a bit more tricky. A formula

    n/2(⌊ n ⌋ + 1) -  ∑ _k=0 ^⌊ n ⌋ 2^k   (n/2^k+1),

 where
 
    (x)  =  min (x - ⌊ x ⌋, ⌈ x ⌉ - x),

 has been derived and thoroughly analyzed in <cit.>. It has been also demonstrated in <cit.> that there is no closed-form formula for B(n).
 
 Incidentally, as it was pointed out in <cit.> , B(n) is equal to the sum A(n,2) of bits in binary representations of all integers < n.








§ A JAVA CODE OF MERGESORT
 

Figure <ref> shows a Java code of MergeSort.






§ GENERATING WORST-CASE ARRAYS FOR MERGESORT
 


Figure <ref> shows a self-explanatory Java code of recursive method unSort that given a sorted array A reshuffles it, in a way resembling InsertionSort[Although not with InsertionSort's sluggishness; the number of moves of keys it performs is only slightly more than the minimum number (<ref>) of comps performed by MergeSort on any n-element array.], onto a worst-case array for MergeSort.






For instance, it produced this array of integers between 1 and 500:




1, 500, 2, 3, 4, 7, 5, 6, 8, 15, 9, 10, 11, 14, 12, 13, 16, 31, 17, 18, 19, 22, 20, 21, 23, 30, 24, 25, 26, 29, 27, 28, 32, 62, 33, 34, 35, 38, 36, 37, 39, 46, 40, 41, 42, 45, 43, 44, 47, 61, 48, 49, 50, 53, 51, 52, 54, 60, 55, 56, 57, 59, 58, 63, 124, 64, 65, 66, 69, 67, 68, 70, 77, 71, 72, 73, 76, 74, 75, 78, 92, 79, 80, 81, 84, 82, 83, 85, 91, 86, 87, 88, 90, 89, 93, 123, 94, 95, 96, 99, 97, 98, 100, 107, 101, 102, 103, 106, 104, 105, 108, 122, 109, 110, 111, 114, 112, 113, 115, 121, 116, 117, 118, 120, 119, 125, 249, 126, 127, 128, 131, 129, 130, 132, 139, 133, 134, 135, 138, 136, 137, 140, 155, 141, 142, 143, 146, 144, 145, 147, 154, 148, 149, 150, 153, 151, 152, 156, 186, 157, 158, 159, 162, 160, 161, 163, 170, 164, 165, 166, 169, 167, 168, 171, 185, 172, 173, 174, 177, 175, 176, 178, 184, 179, 180, 181, 183, 182, 187, 248, 188, 189, 190, 193, 191, 192, 194, 201, 195, 196, 197, 200, 198, 199, 202, 216, 203, 204, 205, 208, 206, 207, 209, 215, 210, 211, 212, 214, 213, 217, 247, 218, 219, 220, 223, 221, 222, 224, 231, 225, 226, 227, 230, 228, 229, 232, 246, 233, 234, 235, 238, 236, 237, 239, 245, 240, 241, 242, 244, 243, 250, 499, 251, 252, 253, 256, 254, 255, 257, 264, 258, 259, 260, 263, 261, 262, 265, 280, 266, 267, 268, 271, 269, 270, 272, 279, 273, 274, 275, 278, 276, 277, 281, 311, 282, 283, 284, 287, 285, 286, 288, 295, 289, 290, 291, 294, 292, 293, 296, 310, 297, 298, 299, 302, 300, 301, 303, 309, 304, 305, 306, 308, 307, 312, 373, 313, 314, 315, 318, 316, 317, 319, 326, 320, 321, 322, 325, 323, 324, 327, 341, 328, 329, 330, 333, 331, 332, 334, 340, 335, 336, 337, 339, 338, 342, 372, 343, 344, 345, 348, 346, 347, 349, 356, 350, 351, 352, 355, 353, 354, 357, 371, 358, 359, 360, 363, 361, 362, 364, 370, 365, 366, 367, 369, 368, 374, 498, 375, 376, 377, 380, 378, 379, 381, 388, 382, 383, 384, 387, 385, 386, 389, 404, 390, 391, 392, 395, 393, 394, 396, 403, 397, 398, 399, 402, 400, 401, 405, 435, 406, 407, 408, 411, 409, 410, 412, 419, 413, 414, 415, 418, 416, 417, 420, 434, 421, 422, 423, 426, 424, 425, 427, 433, 428, 429, 430, 432, 431, 436, 497, 437, 438, 439, 442, 440, 441, 443, 450, 444, 445, 446, 449, 447, 448, 451, 465, 452, 453, 454, 457, 455, 456, 458, 464, 459, 460, 461, 463, 462, 466, 496, 467, 468, 469, 472, 470, 471, 473, 480, 474, 475, 476, 479, 477, 478, 481, 495, 482, 483, 484, 487, 485, 486, 488, 494, 489, 490, 491, 493, 492. 




It took my MergeSort  3,989 comps to sort it. Of course,

    500 ⌈ 500 ⌉ - 2^⌈ 500 ⌉ + 1 = 4,500 - 512 + 1 = 3,989 .





§ NOTES FROM MY ANALYSIS OF ALGORITHMS LECTURE
 

Below are some of the class digital notes I wrote while lecturing Analysis of Algorithms in Spring 2012, with some comments added after class. Figure 4.14 (decision tree) is from the course textbook <cit.>, page 177, showing a decision tree for MergeSort. Note: This figure is copyrighted by Addison Wesley Longman (2000). I used it transformatively in my class for nonprofit education, criticism, and comment  purposes only, and not for any other purpose, as prescribed by U.S. Code Tittle 17 Chapter 1 para 107 that established the “fair use” exception of copyrighted material.




    < g r a p h i c s >
 


    < g r a p h i c s >
 


    < g r a p h i c s >



    < g r a p h i c s >




Below is the improved recursion tree (of the Figure 4.14 page page 177 of <cit.>) that I used in class in Spring 2012.
 


    < g r a p h i c s >


In Spring 2010 and before, I was deriving the equality (<ref>) on page eq:main_level_comps_formula during my lectures directly from the recurrence relation (<ref>), (<ref>) on page eq:recmergesort1.

siam

2017 Marek A. Suchenek. All rights reserved by the author. A non-exclusive license to distribute this article is granted to arXiv.org.

