Gateforum Test Series: Algorithms - Sorting

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?

a)2

b)logn

c)n-1

d)nlogn

Comments

@shaikh yes surely you are right. this is why? i was not sure on my this answer as it is not possible for the real values in real time. with real values we will have different answer what u have given.

---

@Rishav Kumar Singh, @arvin

 if an element compared with every element of the remaining divided array ( divided array should have atleast 2 numbers ) then most compared element of your array should change 

it means

let take array a,b,c,d,e,f,g,h ( consider we are merging )

at first level, we look that array in the angle of one element each

 ....... a.........b.......c.....d......e......f.......g......h........

the next level we have 2 elements each ===> a compared with b

After merginig .....a,b.....c,d.....e,f...g,h....

the next level we have 4 elements each ===> ( an element compared with every element of the remaining divided array ) when will a compared to c and d ? it happens when a is grater than c and d only ===> ( then most compared element of your array should change ) in the sorted array a must be changed it's position to before 'd' or after 'd' 

After merginig .....c,d,a,b.....e,f,g,h.... ===> it can't create more comparissions in further level....

---

@shaikh yes my result was based for worst case comparisons at each level without real values. so it may or may not be valid.

Answer 1

I think , if we want the maximum number of comparisons to be made for an element then let us assume that element to be the comapared is the biggest in the given array , so at level 0 , 2^0 comparison is done

 At level 1, 2^1 comparisons will be done

At level 2, 2^2 comparisons will be done

.

.

.

Similarly at kth level 2^k comparison will be done .

Therefore total number of comparisons made will be summation of all the comparisons.

Plz comment if this analysis is wrong

 

.

Comments

read the comments