Merge sort - maximum comparisons I recently came across a problem where I was to find the maximum comparison operations when applying the merge sort algorithm on an 8 character long string. I tried implementing the 2r^r model however, the number of comparison operations used in a merge sort varies greatly with different input lists. 
My question asked for the greatest number of comparison operations for one list. I applied the r2^r explicit definition which gave me 24. But the answer was 17. I can't find much information online or in the book about elementary algorithms and most solutions do not go into such details.
Does anyone know why this might be? I have seen some solutions where; 
let 2^r = length of list, r2^r = greatest number of comparison operations.
2^r = 8
  r = log(8)/log(2)
  r = 3

Therefore, r2^r = 24

But that is not corroborated in my course. 
any ideas?
 A: Let $a_1...a_8$ be the input and let for simplicity let $ f_{i,j}\begin{cases} 
 1 & \text{if  } a_i\leq a_j \\  0 & \text{if  } a_i> a_j \end{cases}$, i.e. the $f_{i,j}$ are the comparison operations. 
Let us go through the steps of Mergesort; there are 3 levels or phases corresponding to top-down recursive calls:


*

*Level 1 Compute $M(a_1,a_2) , ... ,M(a_7,a_8)$

*Level 2 Merge $(a_1,a_2)$ with $(a_3,a_4) $ and merge $(a_5,a_6)$ with $(a_7,a_8)$

*Level 3 Merge $(a_1,a_2,a_3,a_4) $ with $ (a_5,a_6,a_7,a_8)$
Let us count the # of $f_{i,j}$ at each of the levels


*

*Level 1 has four comparisons $f_{1,2},...,f_{7,8}$

*Level 2 has at most 6 comparisons 


*

*Merge $(a_1,a_2)$ with $(a_3,a_4) $ takes at most 3 comparisons

*Merge $(a_1,a_2)$ with $(a_3,a_4) $ takes at most 3 comaprisons


*Level 3 has at most 7 comparisons $f_{1,5},...,f_{4,8}$


*

*After performing $f_{i,j}$ mergesort will then perform $f_{i,j+1}$ or $f_{i+1,j}$ until it hits $f_{4,8}$; the worst computation path could take 7 comparisons



Let us make an educated guess at the worst-case scenario, say $(7,4,3,6,5,2,1,8)$


*

*Level 1 will spit out $(4,7),(3,6),(2,5)$ and $(1,8)$ after 4 comparisons

*Level 2 will spit out $(3,4,6,7)$ and $(1,2,5,8)$ after 6 comparisons


*

*$(3,4,6,7)$ will cause the comparisons $f_{1,3},f_{1,4},f_{2,4}$ to be computed

*$(1,2,5,8)$ will cause the comparisons  $f_{5,7},f_{5,8},f_{6,8}$ to be computed


*Level 3 will spit out $(1,2,3,4,5,6,7,8)$ after 7 comparisons


*

*The following comparisons will be computed: $f_{1,5},f_{1,6},f_{1,7},f_{2,7},f_{3,7},f_{3,8},f_{4,8}$
For a grand total of 17 
BTW the arguments and construction given can easily be generalized ... do you see the general pattern ... Good Luck with your mathematical voyages! Bon Voyage! 
