Given an array of n distinct numbers, where n = 2^k, how do I find and prove the minimum and maximum number of comparisons?

The comparisons would be between the distinct elements.

I have seen some questions on SO but doesn't seem to match what I'm looking for.

CodePudding user response：

All the comparisons happen during the backtracking step out of recursion, when two adjacent sorted subarrays are merged.

In the best case the two sorted subarrays (each of size