Suppose P, Q, R, S, T are sorted sequences having lengths 20, 24, 30, 35, 50…
2024
Suppose P, Q, R, S, T are sorted sequences having lengths 20, 24, 30, 35, 50 respectively. They are to be merged into a single sequence by merging together two sequences at a time. The number of comparisons that will be needed in the worst case by the optimal algorithm for doing this is ____.
- A.
500
- B.
358
- C.
450
- D.
259
Attempted by 8 students.
Show answer & explanation
Correct answer: B
Concept: The Optimal Merge Pattern is a greedy strategy for merging several sorted sequences into one: at every step, combine the two currently smallest sequences (Huffman-style), since merging two sorted sequences of sizes m and n needs exactly m + n − 1 comparisons in the worst case, and always picking the two smallest available sizes minimizes the total comparisons across all merges.
Application: Applying this to the given sequence lengths (already in ascending order: 20, 24, 30, 35, 50):
Merge the two smallest, 20 and 24, into a sequence of size 44; comparisons = 20 + 24 − 1 = 43. Remaining sizes: 30, 35, 44, 50.
Merge the two smallest, 30 and 35, into a sequence of size 65; comparisons = 30 + 35 − 1 = 64. Remaining sizes: 44, 50, 65.
Merge the two smallest, 44 and 50, into a sequence of size 94; comparisons = 44 + 50 − 1 = 93. Remaining sizes: 65, 94.
Merge the last two sequences, 65 and 94, into a sequence of size 159; comparisons = 65 + 94 − 1 = 158.
Total worst-case comparisons = 43 + 64 + 93 + 158 = 358.
Cross-check: By weighted path length, 20 and 24 each pass through 3 merges, while 30, 35 and 50 each pass through 2 merges. So (20+24)×3 + (30+35+50)×2 = 132 + 230 = 362, and subtracting 1 for each of the 4 merges gives 362 − 4 = 358 — matching the step-by-step total.