Suppose P, Q, R, S, T are sorted sequences having lengths 20, 24, 30, 35, 50…
2014
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 ____.
Attempted by 129 students.
Show answer & explanation
Correct answer: 358
Key idea: merge sequences two at a time using the optimal (Huffman) strategy. Merging two sorted sequences of lengths a and b requires at most a + b - 1 comparisons, so choose merges to minimize the sum of merged sizes.
Merge 20 and 24 → new sequence of length 44 (comparisons: 44 - 1 = 43).
Merge 30 and 35 → new sequence of length 65 (comparisons: 65 - 1 = 64).
Merge 44 and 50 → new sequence of length 94 (comparisons: 94 - 1 = 93).
Merge 65 and 94 → final sequence of length 159 (comparisons: 159 - 1 = 158).
Total comparisons in the worst case = 43 + 64 + 93 + 158 = 358.
Therefore, the optimal algorithm requires 358 comparisons in the worst case.
A video solution is available for this question — log in and enroll to watch it.