Redirected
edited by
2,286 views
2 votes
2 votes
Suppose there are 4 sorted list of 16 elements each. If we merge these lists into a single sorted list of 64 elements. The key comparisons that are needed in the worst case using an efficient algorithm are
edited by

4 Answers

Best answer
6 votes
6 votes
We have to sort 4 lists of size 16 each in a single list using an efficient algo. Here efficient algo means that we should have minimum comparisons.. Now for that we select lists of minimum size and then merge them So first we merge 2 16 sized lists with each other.

In merging the comparisons required in this case(worst case) are 16+16-1(i.e generalization=m+n-1 where m and n are the size of the lists to be sorted )=31.

We merge the other 2 16 sized lists=31 comparisons.

Now we merge the 2 32 sized lists , so no of comparisons are=32+32-1=63

Total no of comparisons are=31+31+63=125 Ans
selected by
4 votes
4 votes

Consider the following tree:

Count the internal nodes = 31+31+63 = 125

1 votes
1 votes
(16+16-1)+(16+16-1) COMPARISIONS IN 1ST PASS OF MERGE ALGO

(32+32-1)  IN  LAST PASS

SO TOTAL 31+31+63=125 ........I THINK
1 votes
1 votes

There are 4 sorted list each of size 100, as n=400
List 1 = 100 records
List 2 = 100 records
List 3 = 100 records
List 4 = 100 records

Combining L1 and L2 needs 16 + 16 - 1 = 31 comparisons, in the worst case.
Combining L3 and L4 needs 16 + 16 - 1 = 31 comparisons, in worst case.

 Now we have two sorted & merged files each of size 200, hence we need 32 + 32 -1 = comparison to merge these files into one file of size 64.

hence total comparisons are required : 2*31 + 63 = 125

Important point: In case of MERGE procedure, if there are two files, one with m records, and second with n records, then we need m+n-1 comparisons in the worst case.

edited by

Related questions

0 votes
0 votes
1 answer
1
Rajat Agrawal007 asked Dec 17, 2018
4,529 views
Which of the following input will give best case time for selection sort?(A) 1 2 3 4 5 6 7 8 9 10(B) 2 3 1 5 9 7 8 6 10(C) 10 9 8 7 6 5 4 3 2 1 (D) All of above take same...
4 votes
4 votes
1 answer
2
Prince Sindhiya asked Aug 23, 2018
1,951 views
. In the standard merge sort algorithm on a list of size n, what is the maximum number of times an item can be compared?a)2b)lognc)n-1d)nlogn
4 votes
4 votes
4 answers
3
Aibi asked Oct 8, 2017
2,578 views
Consider bottom-up merge sort working on 'n' elements. Assume 'n' is a power of 2. The minimum number of comparisons in order to get sorted list is(A) (n log n) / 2(B) n ...