Queues Q.70
- Option : A
- Explanation : Merge-sort combines two given sorted lists into one sorted list. For this problem let the final sorted order be- 1, b, c, d. The two lists (of length two each) should fall into one of the following 3 categories.
(i) a, b and c,d (ii) a, c and b, d (iii) a, d and b, c
The number of comparisons needed in each case will be 2, 3, 3. So, the average number of comparisons will be (2=3+3)/3= 8/3
Here is a better way of doing;
Let list L1 have the items a,c and L2 have the items b,d.
The tree drawn below depicts the different possible cases. (a & b means a is compared with b. If a is smaller, the edge will be labeled a. The number within a circle, beside the leaf nodes, is the number of comparisons, needed to reach it.)
From the tree, we find there are 6 possible ways, the total number of comparisons needed is 3+3+2+2+3+3=16. So, the average number of comparisons is 16/6= 8/3
