edited by
2,583 views
4 votes
4 votes
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 lon n - n + 1
(C) n log n
(D) n log n + n
edited by

4 Answers

10 votes
10 votes
Answer is (NlogN)/2.

Explanation:-

If array has n elements then durring first pass we r merging arrays of size 1. So to merge one pair of array each of size 1 we need 1 comparsion. Number of such pairs n/2. So number of comparsisons n/2 *1=n/2 comparissons.

Now at second level we r merging arrays of size 2. So min number of comparions for  one pair of size 2 array is 2(first element of first array is compared with all  elemnts of second array and all elements of second array gets copied to temporary array and then elements of first array is copied and during this time no comparisons as all elemnts of second array r consumed). So now number of such pairs= n/4. So number of compariosns= n/4*2=n/2. So for each level number of compariosn= (n/(n/2^k))*(2^(k-1))=n/2. So total number of comparisons= n/2 + n/2 + n/2 ... k times. now n=2^k so k=logn. so total numbr of comparions = k*n/2= (logn * n)/2
0 votes
0 votes
2-way bottom-up merge sort the last level (except original array) named as level-1, so on... and let n=2k ===> only k levels present totally

if two sorted arrays have n1 and n2 elements ===> to merge them we require no.of comparissions

1) minimum = n1

2) maximum = n1+n2-1

minimum no.of comparissions required for forming

level 1 :- n21n21 . 1

level 2 :- n22n22 . 2

level 3 :- n23n23 . 4

.

.

.

.

 

level j :- n2jn2j . 2 j-1

 

Total Comparissions = ∑kj=1n2j.2j−1∑j=1kn2j.2j−1 = ∑kj=1n2∑j=1kn2 = n2∑kj=11n2∑j=1k1  = n2(k)n2(k) = n.log(n)2
0 votes
0 votes
ANS - (B)

merging 2 lists having size m and n in sorted way , no of comparisons needed = (m+n-1)

so to merge first n/2 list each of size = 1 comparisons needed = (1+1-1) =  1 for each.

merge first n/4 list each of size = 2 comparisons needed = (2+2-1) = 3 for each. and so on -

therefore -

say k = 2^n

n/2 + 3n/4 + 7n/8 + ....... k times

can anyone ensure is this correct or not ?

Related questions

4 votes
4 votes
1 answer
2
Prince Sindhiya asked Aug 23, 2018
1,955 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
2 votes
2 votes
4 answers
3
Ramij asked Dec 20, 2018
2,287 views
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 ca...
2 votes
2 votes
1 answer
4
smsubham asked Jan 6, 2018
966 views