Solving the recurrence relation for the worst-case number W[n] of comps done by Mergesort 
W[n]==W[⌊(n/2)⌋]+W[⌈(n/2)⌉]+n-1 , W[1]==0

(* Same as
W[n]==W[⌈((n-1)/2)⌉]+W[⌈(n/2)⌉]+n-1 , W[1]==0

RSolve[{W[n]==W[⌊(n/2)⌋]+W[⌈(n/2)⌉]+n-1 , W[1]==0}, W[n], n]

Mathematica can't do it!

(But it can plot it - we will plot it later)

Assume n = (2^k)and put A[k] = W[n].
We have k = (Subscript[log, 2])n, so

W[n] = A[(Subscript[log, 2])n]

W[n]==W[⌊(n/2)⌋]+W[⌈(n/2)⌉]+n-1 , W[1]==0

becomes

W[(2^k)]==W[((2^k)/2)]+W[((2^k)/2)]+(2^k)-1 , W[1]==0

or

W[(2^k)]==W[(2^(k-1))]+W[(2^(k-1))]+(2^k)-1 , W[1]==0

or

W[(2^k)]==2W[(2^(k-1))]+(2^k)-1 , W[(2^0)]==0

or

A[k]==2A[k-1]+(2^k)-1 , A[0]==0

RSolve[{A[k]==2A[k-1]+(2^k)-1 , A[0]==0}, A[k], k]

So,

W[n] =A[Log2[n]]=
1-(2^(Log2[n]))+(2^(Log2[n])) Log2[n]=
1-n+n Log2[n]=
 n Log2[n] - n + 1 = n( Log2[n]-1) + 1

Since W[n] is integer for every n (not just for n = (2^k)), one can infer that

 ⌈n( Log2[n]-1) + 1⌉≤ W[n]

This is the lower bound from the textbook, Theorem 4.6. (correctly derived here).

Plot of the exact solution

We use M instead of W here for purely technical reasons.

M[1]=0;

M[n_]:=M[⌊(n/2)⌋]+M[⌈(n/2)⌉]+n-1 ;

Table[{n,M[n]},{n,1,50}]

DiscretePlot[Tooltip[{M[n]}],{n,1,2000}]

We showed in file http://csc.csudh.edu/suchenek/CSC401/Slides/MergeSort_note.pdf that
 W[n]=(∑_(i=1)^n)⌈Log2[i]⌉
is the solution of the recurrence relation on M[n]. Below is a graph of both functions. Since they coincide, M[n]+10 is plotted in lieu of M[n] to show that there are two graphs there.

DiscretePlot[Tooltip[{M[n]+10,(∑_(i=1)^n)⌈Log2[i]⌉}],{n,1,200}]

Ploting the exact solution against textbook lower bound and upper bound:

DiscretePlot[Tooltip[{M[n],⌈n Log2[n]-n+1⌉,⌈n Log2[n]-.914n⌉}],{n,790,1030}]

DiscretePlot[Tooltip[{M[n],⌈n Log2[n]-n+1⌉,⌈n Log2[n]-.914n⌉}],{n,1220,1410}]

DiscretePlot[Tooltip[{M[n],⌈n Log2[n]-n+1⌉,⌈n Log2[n]-.914n⌉}],{n,1950,2100}]

However, for n = 11, the worst-case number of comparisons done by Mergesort is 29 while the textbook claims it is no more than 28. (Other values of for which the textbook upper bound is incorrect are 22, 44, 88, 89,176 through 179, 352 through 358, 703 through 716,1406 through 1433, and more ...)

Table[Tooltip[{n,n (Log2[n]+ϵ[n]-1)+1,⌈n Log2[n]-.914n⌉}],{n,10,12}]

{{10,25,25},{11,29,28},{12,33,33}}

Table[Tooltip[{n,M[n],n (Log2[n]+ϵ[n]-1)+1,⌈n Log2[n]-.914n⌉}],{n,1406,1433}]

{{1406,13419,13419,13418},{1407,13430,13430,13429},{1408,13441,13441,13440},{1409,13452,13452,13451},{1410,13463,13463,13462},{1411,13474,13474,13473},{1412,13485,13485,13484},{1413,13496,13496,13495},{1414,13507,13507,13506},{1415,13518,13518,13517},{1416,13529,13529,13528},{1417,13540,13540,13539},{1418,13551,13551,13550},{1419,13562,13562,13561},{1420,13573,13573,13572},{1421,13584,13584,13583},{1422,13595,13595,13594},{1423,13606,13606,13605},{1424,13617,13617,13616},{1425,13628,13628,13627},{1426,13639,13639,13638},{1427,13650,13650,13649},{1428,13661,13661,13660},{1429,13672,13672,13671},{1430,13683,13683,13682},{1431,13694,13694,13693},{1432,13705,13705,13704},{1433,13716,13716,13715}}

Other than that, the textbook bounds, although not well-derived, is really good!

The solution of the textbook's recurrence relation on W(n) 
 
W(n)=n lg n -(α - lg α)n +1

in the proof of Theorem 4.6 p. 177 (although not well-derived) is equal to ours
n (lg n+ϵ-1)+1, or
n lg n+(ϵ-1)n+1.

α[x_]:=(2^(⌊Log2[x]⌋-Log2[x]+1));
Plot[Tooltip[{n (Log2[n]+ϵ[n]-1)+1+10 (*added to see 2 graphs*),n Log2[n]-(α[n]-Log2[α[n]])n+1}],{n,2,100}]

Here is the exact solution derived in class.

W[n] = n(⌊Log2[n]⌋+1)-(2^(⌊Log2[n]⌋+1))+1=
(=(∑_(i=1)^n)⌈Log2[i]⌉=)
 =n⌊Log2[n]⌋-(2^(⌊Log2[n]⌋+1))+n+1=
=n⌊Log2[n]⌋-(2^(⌊Log2[n]⌋+1))+2+n-1=
=(∑_(i=1)^(n-1))⌊Log2[i]⌋+n-1=
=n (Log2[n]+ϵ[n])-2 (n-1)+n-1=
=n (Log2[n]+ϵ[n])-n+1=
=n (Log2[n]+ϵ[n]-1)+1

where

β[x_]:=1+x-(2^x)

θ[x_]:=⌈x⌉-x

ϵ[x_]:=β[θ[Log2[x]]]

Here is a plot of function ϵ[n]

Plot[{ϵ[n],.0860,.5},{n,1,1000},AspectRatio->.13]

So

n (Log2[n]+0)-n+1≤ W[n]<n (Log2[n]+.0861-1)+1=n (Log2[n])-0.9139n+1

(So, the textbook approximation 
W[n]≤ ⌈n Log2[n]-.914n⌉
yielded slightly incorrect (too small) upper bound (for some n.)

Here is the plot of the exact solution and its bounds:

Plot[{n (Log2[n]+ϵ[n]-1)+1,n (Log2[n]+0-1)+1,n (Log2[n]+.0861-1)+1},{n,1,20}]

Plot[{n (Log2[n]+ϵ[n]-1)+1,n (Log2[n]+0-1)+1,n (Log2[n]+.0861-1)+1},{n,1,4}]

Plot[{n (Log2[n]+ϵ[n]-1)+1,n (Log2[n]+0-1)+1,n (Log2[n]+.0861-1)+1},{n,127,257}]

The rest of this file is optional for all students.

Note: The best-case number comparisons for QuickSort is the same as the worst-case number of comparisons for MergeSort: the respective formula can be derived using the same recursion tree.

(* The above note was removed because it was not true. 
The worst-case number of comparisons done by MergeSort is (∑_(i=1)^n)⌈Log2[i]⌉ while 
the best-case number of comparisons done by Quicksort is (∑_(i=1)^n)⌊Log2[i]⌋, so the difference between the two is
(∑_(i=1)^n)⌈Log2[i]⌉-(∑_(i=1)^n)⌊Log2[i]⌋=
[by the formula in file 
/media/Suchenek/Courses/CSC401/Website/Slides/Knuth-Suchenek_formulas_sums_of_floors_ceilings_logs.pdf] 
=n-⌊Log2[n]⌋-1.

(* The recurrence relation for the latter is:

(*
A[n]==A[⌊((n-1)/2)⌋]+A[⌈((n-1)/2)⌉]+n-1 , A[1]==0

(* which is the same as
A[n]==A[⌊((n-1)/2)⌋]+A[⌊(n/2)⌋]+n-1 ,A[1]==0

(* so it is not the same (although very close) as the recurrence relation for the former
W[n]==W[⌈((n-1)/2)⌉]+W[⌈(n/2)⌉]+n-1 , W[1]==0

Below is a plot of the worst-case for MergeSort together with the average-case for QuickSort and its approximation.

For all n ≤ 12,the number of comparisons performed by MergeSort in the worst case is equal to the ceiling of   the average number of comparisons performed by QuickSort.

∀n≤ 12, (Subscript[W, MergeSort])[n]=⌈(Subscript[A, QuickSort])[n]⌉



MergeSort performs less comparisons in the worst case than QuickSort on the average for all n ≥ 13.
∀n≥ 13, (Subscript[W, MergeSort])[n]<(Subscript[A, QuickSort])[n]

12!

So, it is feasible to test exhaustively the above fact.

Here is a demonstration of the above facts.

(∑_(j=1)^n)(1/j)

Plot[{n (Log2[n]+ϵ[n])-n+1, N[2 (n + 1) HarmonicNumber[n] - 4 n]},{n,10,20},PlotPoints->200]

Table[{n,{n (Log2[n]+ϵ[n])-n+1, N[2 (n + 1) ((∑_(j=1)^n)(1/j)) - 4 n]}},{n,1,20}]

Plot[{n (Log2[n]+ϵ[n])-n+1, 2 (n + 1) ((∑_(j=1)^n)(1/j)) - 4 n,1.386 n Log2[n+1]-2.846 n},{n,1,50},PlotPoints-> 100]

Plotting formula  
n(⌊Log2[n]⌋+1)-(2^(⌊Log2[n]⌋+1))+1
derived in class

DiscretePlot[Tooltip[{n(⌊Log2[n]⌋+1)-(2^(⌊Log2[n]⌋+1))+1}],{n,1,200}]

Ploting the formula  
n(⌊Log2[n]⌋+1)-(2^(⌊Log2[n]⌋+1))+1  
derived in class and the exact solution (they coincide!):

DiscretePlot[Tooltip[{M[n],n(⌊Log2[n]⌋+1)-(2^(⌊Log2[n]⌋+1))+1}],{n,1950,2100}]

Ploting the difference between the formula 
n(⌊Log2[n]⌋+1)-(2^(⌊Log2[n]⌋+1))+1 
 derived in class and the exact solution (it's zero!):

Here is a plot of the difference (zero) between the two

DiscretePlot[{n(⌊Log2[n]⌋+1)-(2^(⌊Log2[n]⌋+1))+1-M[n]},{n,1950,2100}]

DiscretePlot[{n(⌊Log2[n]⌋+1)-(2^(⌊Log2[n]⌋+1))+1-M[n]},{n,1,200}]

Ploting the formula  
n (Log2[n]+ϵ[n]-1)+1  
and the exact solution (they coincide!):

DiscretePlot[Tooltip[{M[n],n (Log2[n]+ϵ[n]-1)+1}],{n,1,100}]

The best case for QuickSort

It happens when all pivots are the median of respective ranges.

Recurrence relation:

B[0]:=0

B[1]:=0

B[n_]:=n-1+B[⌊((n-1)/2)⌋]+B[⌈((n-1)/2)⌉]

The solution is:

B[n]=(∑_(i=1)^n)⌊Log2[i]⌋=
(n+1)⌊Log2[n]⌋-(2^(⌊Log2[n]⌋+1))+2

DiscretePlot[{B[n]+1,(∑_(i=1)^n)⌊Log2[i]⌋},{n,1,50}]

Below is a plot of the worst-case for MergeSort together with the best-case for QuickSort.

For all n =6,the number of comparisons performed by MergeSort in the worst case is equal to the best number of comparisons performed by QuickSort.

(Subscript[W, MergeSort])[6]=(Subscript[B, QuickSort])[6]

Moreover,

∀n< 6, (Subscript[W, MergeSort])[n]<(Subscript[B, QuickSort])[n]


MergeSort performs more comparisons in the worst case than QuickSort in the best case for all n >6.

∀n> 6, (Subscript[W, MergeSort])[n]>(Subscript[B, QuickSort])[n]

Best case for Mergesort is when the shorter array sent to merge has all smaller elements than the larger one. This yields the recurrence relation:

BM[0]:=0

BM[1]:=0

BM[n_]:=⌊(n/2)⌋+BM[⌊(n/2)⌋]+BM[⌈(n/2)⌉]

DiscretePlot[{B[n],BM[n],M[n]},{n,1,50},PlotTheme->"Classic"]

DiscretePlot[{B[n],BM[n],M[n]},{n,1,200},PlotTheme->"Classic"]

Interesting fact (optional for all students)

Consider BinaryInsertionSort that works like InsertionSort except that it runs the standard binary search algorithm in order to determine the place for an insertion of the next element.

This does not save any moves of keys that still need to be shifted up in order to make a room for insertion but it saves quite a lot of comparisons of keys in the worst case.

Since the number of comparisons of keys performed in the worst case while inserting a key into an ordered array of i keys is now the same as the number of comparisons of keys that the Binary Search performes in the worst case while searching for a key in an ordered array of i keys, the former is equal to

⌊Log2[i]⌋+1=⌈Log2[i+1]⌉.

Thus the number of comparisons of keys performed in the worst case by BinaryInsertionSort is the sum of the above with i ranging from 0 (inserting the first key into an empty array) to 
n-1 (inserting the last n-th key into an 
n-1-element array. This is equal to

(∑_(i=0)^(n-1))⌈Log2[i+1]⌉=(∑_(i=1)^n)⌈Log2[i]⌉=

n⌈Log2[n]⌉-(2^(⌈Log2[n]⌉))+1.

So, the number of comaprisons of keys performed by the BinaryInsertionSort in the worst case is exactly the same as the number of comaprisons of keys performed by the Mergesort in the worst case!