Register

Comparisons for merging four arrays

3,751 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 ____.
User Avatar

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
User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

11.8k
views
2 answers
0 votes
radha gogia asked Jul 31, 2015
11,846 views
A average number of comparison performed by the merge sort algorithm ,In Merging two sorted lists of length 2 is
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 ... have merged both the lists , so then how to calculate the average no of comparisons here ?
User Avatar
317
views
1 answers
0 votes
Kamalkant Patel asked Jan 30, 2016
317 views
merge algo
Number of comparisions in worst case required to merge two sorted arrays of size 40 and 60 are-------
User Avatar
712
views
1 answers
1 votes
Rajesh R asked Nov 9, 2017
712 views
Number of comparisons (previous gate question)
Atmost how many comparisons are required to find out min and max in an array of n elements where n is even ?Answer is atmost 1.5n - 2 comparisons.For n=6, I tried manually ... 1.5(6) - 2 =7 which is lesser than 8 !Where am I going wrong ?
User Avatar
Link Copied!