MADEEASY

Question

Consider bottom- up merge sort working on 'n' elements . Assume n is a power of 2. The MAXIMUM number of comparisons in order to get sorted list is

Comments

that is using optimal merge pattern(greedy algorithm)

but in the question, it is bottom-up merge sort(divide and conquer algorithm)

---

(1,5), (3,7) for merging

1 is compared with 3

5 is compared with 3

5 is compared with 7

total =3, after that it produce (1,3,5,7)

 

(2,6),(4,8) for merging

2 is compared with 4

6 is compared with 4

6 is compared with 8

total=3, after that it produce (2,4,6,8)

 

grand total for merging at level 2 = 3 + 3 = 6

continue this process....

 

if required i will add general procedure also for concluding my value

---

ShaikMastan sir....u r correct

if taken bottom up merge sort, wher we starting sorting by taking adjcent elements from below and go upt we get 1 comparison for each pair and n/2 pairs so n/2 comparison at bottom most level...then we move 1 level up and then we have maximum 3 comparisons and then we will have n/4 pairs so total comaparisons will be 3*(n/4)...like wise move upto height of tree which is logn then we get a equation which if  solve will get your answer

i took this when elements are in power of 2 ..

---

@Navneet Kalra

exactly that is the procedure.

Moreover no need to call me sir.