1
$\begingroup$

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?

$\endgroup$
12
  • $\begingroup$ What distinguishes this "cardinality" of comparison operations from the computational complexity of the merge sort, which in computer science is usually measured by the number of comparison operations performed? How is any computation complexity problem not a "discrete maths question on cardinality" according to your definition? $\endgroup$
    – David K
    Apr 29 '20 at 2:25
  • $\begingroup$ Perhaps it would help if you showed, step by step, how you arrived at the answer $24$ so people can see how your methods reflect some kind of discrete maths cardinality approach instead of a computer science complexity approach. It would be better if you write the math in math notation; see math.stackexchange.com/help/notation $\endgroup$
    – David K
    Apr 29 '20 at 2:27
  • $\begingroup$ I distinguished it from a computer science problem as my understanding is that their implementations are different. In my experience, I use merge sort in Java or C++ to combine two lists and sort them in one function. You are right, the complexity of which would determine the worst-case/ greatest number of comparisons. However, the question specified one list of 8 elements which I am not used to. $\endgroup$
    – Ventti
    Apr 29 '20 at 3:31
  • $\begingroup$ Thanks, David I just added my method I used to find 24. I also removed the disclaimer. $\endgroup$
    – Ventti
    Apr 29 '20 at 3:35
  • $\begingroup$ Complexity theory in computer science involves no Java or C++. It's an abstract topic. But computer science also is a topic on this site, as you can see by searching the [computer-science] tag. $\endgroup$
    – David K
    Apr 29 '20 at 3:41
1
$\begingroup$

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:

  1. Level 1 Compute $M(a_1,a_2) , ... ,M(a_7,a_8)$
  2. Level 2 Merge $(a_1,a_2)$ with $(a_3,a_4) $ and merge $(a_5,a_6)$ with $(a_7,a_8)$
  3. 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

  1. Level 1 has four comparisons $f_{1,2},...,f_{7,8}$
  2. 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

  3. 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)$

  1. Level 1 will spit out $(4,7),(3,6),(2,5)$ and $(1,8)$ after 4 comparisons
  2. 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
  3. 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!

$\endgroup$
2
  • 1
    $\begingroup$ Okay yep, that's a great explanation. I see how they arrived at 17 now. I was quite confused. We have just covered proofs for strong induction, so I think I can induce an explicit formula from your solution that can solve for the greatest number of comparison operations. However, without skipping a beat we are now combining: Probability, propositional logic, matrices and algorithms - so RIP me. But knowing I can count on my math stack exchange community to help me out here and there gives me the confidence to continue strong on my mathematical voyage. Thank you Pedrpan !! $\endgroup$
    – Ventti
    Apr 29 '20 at 15:07
  • $\begingroup$ No problem, I am glad that I could be of use to you! Take care! $\endgroup$ Apr 29 '20 at 20:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.