Merge Sort Comparisons

Question

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

a)2

b)logn

c)n-1

d)NOT

My doubt is here ,Are we considering a specific Item throughout our Analysis.?

Answer 1

Let us consider n=2^k

let at level i , L1 and L2 is merged,

An item in L1 is compared maximum times when all the items in L2 is less than item in L1.

Say at leaf level k (level at smallest subproblem having one element in each list), an item is compared only once when merging.

at level k-1  an item is compared twice when merging.

say at level i , it is compared n/2ⁱ times

at level 2 it is compare n/2 times and after merging we get the sorted array of our problem

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

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

                                          = n - n/(2^k)

                                          = n-1

Answer is c) n-1.

Correct me if I am Wrong

Comments

yeah got it, Nice Explanation Thanks :)

---

Its welcome.

---

min number of times is logn, right?

---

I think min is 1.
Ex

[3] [4] , [5], [6]

let consider the element 6
[3,4] [5,6]      6 is compared 1 time

[3,4,5,6]        6 is compared 0 time.

So , min no of comparison of an element is 1

Correct me if I am wrong.

Answer 2

in maximum case n-1 compare

Answer 3

the answer will be (n-1). Take any array and compute the sort with the worst case.you will get it!