#GATE

Question

There are 4 sorted lists of n/4 elements each. If we merge these lists into a single sorted list of n elements , for the n=400 number of key comparison in the worst case using an efficient algorithm is?

Answer 1

To merge two sorted list just compare the smallest elements of both list and put smallest element to merged list and remove the selected element from the list and repeat until you get one of the list empty and just copy the another list as it is. This can be done in linear time and worst case will appear when we have to compare the last elements of both list in that case $m+n-1$ comparisions needed.

consider 4 list named 1, 2, 3 & 4 each having $\frac{n}{4}$ elements
Merge 1 and 2 -->comparisions needed = $\frac{n}{4}+ \frac{n}{4} - 1 = \frac{n}{2} - 1$
Merge 3 and 4 -->comparisions needed = $\frac{n}{4}+ \frac{n}{4} - 1 = \frac{n}{2} - 1$

now 1-2 and 3-4 will contain $\frac{n}{2}$ elements each
Merge 1-2 and 3-4 -->comparisions needed = $\frac{n}{2}+ \frac{n}{2} - 1 = n - 1$

$\therefore$, total comparisions needed = $\frac{n}{2} - 1+\frac{n}{2} - 1+n-1 =  2n - 3 $
for n = 400 , comparisions needed = 2(400) - 3 = 797

Answer 2

to merge two liast of m,n number of comparison needed M+N-1

now 4 sorted list of 100 elements

to merge two 100 list no of comparison needed 100+100-1=199

rest 2 100 element list=100+100-1=199

now two 200 element list ,so comparison=200+200-1=399

 

now add all 199+199+399=797

Answer 3

Answer is 797.