3,328 views
6 votes
6 votes

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.?

3 Answers

10 votes
10 votes

Let us consider n=2k

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/2i 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/(22)+. . . . +   .n/(2k)    where n/(2k) =1

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

                                          = n - n/(2k)

                                          = n-1

Answer is c) n-1.

Correct me if I am Wrong

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

Related questions

0 votes
0 votes
0 answers
2
Nandkishor3939 asked Jan 21, 2019
679 views
What is the extra memory needed for merge sort:1] In case of Iterative merge sort.(DS:Array)2]In case of Recursive merge sort.(DS:Array)3] In case of Iterative merge sort...
0 votes
0 votes
0 answers
3
Vikas123 asked Jan 8, 2019
1,003 views
Can anyone help me to understand this problem….??
0 votes
0 votes
1 answer
4
Abhisek Tiwari 4 asked Nov 24, 2018
626 views
no of comparisons in merge sort max?how many max no swaps??[if inplace algo]