GATE CS 2014 Set 2 Q38 — Searching, Sorting, Hashing

To find the minimum number of comparisons in the worst case to merge multiple sorted sequences, we use an optimal merge pattern (similar to Huffman's greedy approach).

Key Principle

When merging two sorted sequences of sizes $m$ and $n$, the number of comparisons required in the worst case is:

To minimize the total number of comparisons, we greedily select the two smallest sequences at each step to merge.

Step-by-Step Merging

The initial sizes of the sequences are: $\{20, 24, 30, 35, 50\}$.

1. Merge the two smallest sequences: $20$ and $24$.
   • New sequence size: $20 + 24 = 44$
   • Worst-case comparisons: $20 + 24 - 1 = 43$
   • Remaining sizes: $\{30, 35, 44, 50\}$
2. Merge the two smallest sequences: $30$ and $35$.
   • New sequence size: $30 + 35 = 65$
   • Worst-case comparisons: $30 + 35 - 1 = 64$
   • Remaining sizes: $\{44, 50, 65\}$
3. Merge the two smallest sequences: $44$ and $50$.
   • New sequence size: $44 + 50 = 94$
   • Worst-case comparisons: $44 + 50 - 1 = 93$
   • Remaining sizes: $\{65, 94\}$
4. Merge the remaining two sequences: $65$ and $94$.
   • New sequence size: $65 + 94 = 159$
   • Worst-case comparisons: $65 + 94 - 1 = 158$

Total Comparisons

Summing the comparisons from each step:

Thus, the minimum number of comparisons needed in the worst case is 358.