GATE CSE
First time here? Checkout the FAQ!
x
0 votes
52 views

asked in Algorithms by Boss (6.2k points)   | 52 views

1 Answer

+4 votes
Best answer

In worst case, number of comparisons to merge two sorted lists of size m and n is m+n-1.

We take two lists of size 8 each, and merge them into a list of size 16. Comparisons needed = 8+8-1 = 15.

Similarly, to merge the other two lists of 8 elements, comparisons needed = 15.

We have two lists of size 16 and 16 now.

To merge them to a list of size 32, number of comparisons needed = 16+16-1 = 31.

Total comparisons = 15 + 15 + 31 = 61.

NOTE: In best case, we need max(m,n) comparisons. It happens when the last element of the first list is smaller than the first element of the second list.

answered by Boss (8.1k points)  
edited by
so nicely explained..thanx a lot..:)
welcome!


Top Users Aug 2017
  1. ABKUNDAN

    4660 Points

  2. Bikram

    4366 Points

  3. akash.dinkar12

    3258 Points

  4. rahul sharma 5

    3042 Points

  5. manu00x

    2682 Points

  6. makhdoom ghaya

    2410 Points

  7. just_bhavana

    2100 Points

  8. Tesla!

    1918 Points

  9. stblue

    1682 Points

  10. joshi_nitish

    1608 Points


24,928 questions
32,024 answers
74,385 comments
30,113 users