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 $\underline{\hspace{1cm}}$.

To merge two sorted sequences of sizes $m$ and $n$, the maximum (worst-case) number of comparisons required is:

To minimize the total number of comparisons, we use the Optimal Merge Pattern (a greedy Huffman-like approach), repeatedly selecting the two sequences of smallest length to merge.

### Step-by-step Merging:

Initial list of lengths: $\{20, 24, 30, 35, 50\}$

1. First Merge:

   • Choose the two smallest: $20$ and $24$.

   • New sequence size: $20 + 24 = 44$.

   • Worst-case comparisons: $20 + 24 - 1 = 43$.

   • Remaining lengths: $\{30, 35, 44, 50\}$.

2. Second Merge:

   • Choose the two smallest: $30$ and $35$.

   • New sequence size: $30 + 35 = 65$.

   • Worst-case comparisons: $30 + 35 - 1 = 64$.

   • Remaining lengths: $\{44, 50, 65\}$.

3. Third Merge:

   • Choose the two smallest: $44$ and $50$.

   • New sequence size: $44 + 50 = 94$.

   • Worst-case comparisons: $44 + 50 - 1 = 93$.

   • Remaining lengths: $\{65, 94\}$.

4. Fourth Merge:

   • Merge the last two: $65$ and $94$.

   • New sequence size: $65 + 94 = 159$.

   • Worst-case comparisons: $65 + 94 - 1 = 158$.

### Total Worst-Case Comparisons: