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

asked in Algorithms by Boss (7k points) 5 32 85 | 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 Veteran (10.2k points) 6 44 108
edited by
so nicely explained..thanx a lot..:)
welcome!

Related questions

0 votes
2 answers
1
asked in Algorithms by Shubhanshu Boss (9.2k points) 5 41 148 | 246 views
+3 votes
1 answer
2
asked in Algorithms by Arnabi Boss (7k points) 5 32 85 | 103 views
+1 vote
0 answers
3
asked ago in Algorithms by rahul sharma 5 Veteran (15k points) 13 112 320 | 62 views


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Top Users Oct 2017
  1. Arjun

    23684 Points

  2. Bikram

    17288 Points

  3. Habibkhan

    9194 Points

  4. srestha

    6486 Points

  5. Debashish Deka

    5478 Points

  6. jothee

    5168 Points

  7. Sachin Mittal 1

    4910 Points

  8. joshi_nitish

    4504 Points

  9. sushmita

    4080 Points

  10. Rishi yadav

    3998 Points


Recent Badges

Nice Comment Pooja Palod
Famous Question Harsh181996
Verified Human ASK
Good Comment Bikram
Good Comment Arjun
Nice Comment Arjun
Famous Question Meenakshi Sharma
Famous Question Meenakshi Sharma
Nice Question smartmeet
Nice Comment Vicky rix
27,426 questions
35,275 answers
84,602 comments
33,523 users