GATE 2014 CS (CS2) – Question 48
Sorted sequences P,Q,R,S,T have lengths 20,24,30,35,50. Merge them into one by merging two sequences at a time. Find worst-case comparisons for an optimal algorithm.
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 358 to 358
Explanation
Greedily merge the two shortest lengths:20+24=44 costs43comparisons;30+35=65 costs64. Then44+50=94 costs93, followed by65+94=159 costs158. Total43+64+93+158=**358** in the worst case. Each merge of lengths a,b needs at most a+b−1comparisons.