Merge Sort

Question

In the standard merge sort algorithm on a list of size n, what is the maximum number of times an item can be compared?

Comments

Items of size 1---> n/2-1

Items of size 2---> n/2 -1

for size 4->> n/2 -1

Continue this for logn times

=> n/2 + n/2 +n/2 + .... logn times - logn

=> n/2 * logn - logn comparisons are required

Answer 1

The element be let in any of these 2^k elements  and once our element is compared within sub-array , it will not again compared with any element within sub-array again.

Total comparison of an item = n/2+ n/(2^2)+. . . . +  n/(2^k)    where n/(2^k) =1

                                          = n*(1-1/(2^k))

                                          = n - n/(2^k)

                                          = n-1