Chapter 4, Analysis of MergeSort


5. What is the necessary and sufficient condition for the subarrays that are to be merged which will force Merge to perform the maximum number (n - 1, that is) of comparisons of keys?

Answer: None of those subarrays contains the two largest elements of the resulting merged array.