3,518 views
2 votes
2 votes
Suppose there are 4 sorted lists of 8 elements each. If we merge these lists into a single sorted list of 32 elements. The key comparisons that are needed in the worst case using an efficient algorithm are ____.

4 Answers

0 votes
0 votes
I got answer as 48.

my logic-

there are 4 lists with 8 sorted elements.

lets pick all the first four and compare them to find smallest. that would be 3 comparisons.

to find the 2nd smallest it would require 2 comparisons and 1 comparison to find 3rd smallest.

therefore 3+2+1=6 comparisons in total.

if we do this 8 times we will get 6*8=48

what's the flaw in this logic?

Nevermind  i know now why it's wrong
edited by

Related questions

0 votes
0 votes
2 answers
2
radha gogia asked Jul 31, 2015
11,500 views
If I have two lists of length 2 then no of comparisons in the worst case would be 2 only , since If I have say 10,20 in list A and 5,7 in list B so then on merging 10 is ...
0 votes
0 votes
1 answer
3
Kamalkant Patel asked Jan 30, 2016
279 views
Number of comparisions in worst case required to merge two sorted arrays of size 40 and 60 are -