Ace Test Series: Algorithms - Sorting

Question

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

Answer 1

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

Comments

Consider two sorted arrays 1234, 5678

Isn't minimum number of comparisons 1, i.e. when last element of 1st array is greater than first element of 2nd array (if 4 > 5)?

Answer 2

Is C the correct solution?..

Comments

A is the correct answer.

Answer 3

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

Answer 4

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 ?

Comments

you are considering max number of comparisons which is=m+n-1;

we need min number of comparison which is=min(m,n).