Data Structures

Answer : 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, 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, total number of comparisons needed is 3+3+2+2+3+3=16. So, average number of comparisons is 16/6= 8/3.