3,086 views
2 votes
2 votes
To merge two lists of size m and n, how many comparisons we need to perform in the worst case and best case respectively ?

a) m+n-1 and m+n-1

b)m+n+1 and max(m,n)

c)max(m,n) and min(m,n)

d)m+n-1 and min(m,n)

 

can someone give the worst case and best case  with examples ?

2 Answers

Best answer
3 votes
3 votes

Let us take two sorted lists A and B .. In merging of two sorted list to make a third list , we do the following .

a) We start from first elements of A and B..Set one pointer to keep track of A and one for B..Initialise both pointers to the respective first elements.

b) We compare current element of A with current element of B which is determined by respective points..Now three cases arise :

  •         If  current element of A < B , then copy the current element of A to third list C and then increment pointer of A to point to its next element..
  •         If  current element of B < A , then copy current element of B then increment pointer of B..
  •         If both current elements are same , then we copy the element and increment both lists' pointers.

c) The above step is repeated till the end of one of the list is not reached..After which the remaining elements of A or B [depending on which list has more elements]  are copied to the third list C without any comparison as the end of one of the lists is reached hence nothing to compare with is left..

d) Now if we see number of move operations to third list C will be same irrespective of the distribution of values in lists A and B..And this is nothing but total number of elements of A + number of elements of B  =   m + n [ Assuming A has m elements and n elements ]

e) Now for number of comparison it will differ though.This depends on how early we reach to one of the lists' end .Lets see the two cases :

  • It may happen that while comparison the smaller element always happens to come from the same list and that too from the list which has less number of lists..So in this case the number of comparison is determined by the shorter list length as once its end is reached , no more need of comparison..Hence best case scenario = min(m,n).
  • On the other hand , in worst case the length of the two lists will be same and each time we compare the elements of list , [one element of list A compared with that of list B] , and at each step the minimum of two comes come from the list alternately , i.e. if at first step the minimum came from list A , the next time we will have minimum from B , then from A and so on]..So number of comparisons here  =  n + n - 1  =  2n - 1..Generalising it to m and n , we get number of comparisons  = m + n - 1

Hence D) should be the correct option.. 

selected by
2 votes
2 votes

Ans D

1.For worst case take these two list

A- 10,20,30,40 & B-11,21,31,41

When we apply merge algo on these two list then element get  sorted alternatively from these lists.

1.compare 10&11-10

2.compare 20&11-11

3.compare 20&21-20

4.compare 30&21-21

5. compare 30&31-30

6. compare 40&31-31

7. compare 40,41-40

& last 41

Sorted list will be - 10,11,20,21,30,31,40,41

Total comparison= m+n-1=4+4-1=7

2Best Case - In this case elements of one list get sorted first by comparing and for sorting remaining elements of second list needs no comparison because they are already sorted. 

A= 10,20   B-30,40,50,60,70 

1.Compare 10&30-10

2.Compare 20&30-20

and then no comparison for 30 40 50 60 70

Total comparison=min(m,n)=min(2,5)=2

Related questions

5 votes
5 votes
5 answers
1
Satbir asked Jan 13, 2020
7,670 views
If an array $A$ contains the items $10,4,7,23,67,12$ and $5$ in that order, what will be the resultant array $A$ after third pass of insertion sort?$67,12,10,5,4,7,23$$4,...
3 votes
3 votes
4 answers
2
Satbir asked Jan 13, 2020
3,340 views
Of the following sort algorithms, which has execution time that is least dependant on initial ordering of the input?Insertion sortQuick sortMerge sortSelection sort
0 votes
0 votes
3 answers
3
pankaj_vir asked Oct 10, 2018
1,210 views
What is the total number of comparisons needed in the best case to find minimum and maximum of $300 $ elements?
5 votes
5 votes
1 answer
4
shaurya vardhan asked Nov 4, 2017
8,103 views
You are given an array of 64 elements, minimum number of comparisons required to find out second largest element among all will be _______.