Let Ll, for 1 ≤ i ≤ 4, be four lists of numbers, each sorted in ascending order. The numbers of entries in these lists are 75, 40, 110, and 50, respectively.
(a) How many comparisons are needed to merge these four lists by merging L1 and L2, merging L3 and L4, and then merging the two resulting lists?
(b) How many comparisons are needed if we first merge L1 and L2, then merge the result with L3, and finally merge this result with L4?
(c) In order to minimize the total number of comparisons in this merging of the four lists, what order should the merging follow?
(d) Extend the result in part (c) to n sorted lists L1, L2,..., Ln.