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______?
First take P and Q(These two are min length) and merge them with merge sort, then max no. of comparisons will be 20 and max 4 elements will be copied directly.New list will have 44 elements let this be list A.
Secondly, take list R and S and merge them .Here max comparisons will be 30 .let this list be B.
Now merge list A and T. max comparisons here will be 44.let this list be C
lastly merge B and C with max comparisons equal to 65.
therefore total number of comparisons that will be needed in the worst case by the optimal algorithm for doing this is 20+30+44+65=159.