Average merge time: An intuitive interpretation

A classical result by Nagler states that the average comparison time of the standard merge algorithm over merge pairs of size n, i.e. pairs of sorted lists of size n, is:T_M(n,n) = 2n²n+1 Nagler's proof sheds little light on the intuition which should be given to this quotient. We provide an intuitive interpretation of Nagler's result, based on the notion of an "alternation". This notion essentially represents a switch between the two lists in mergings "pop-the-top" process. We recall from ([2]) that the average number of alternations over all possible merge pairs of size n is n and provide a simplified proof of this fact. We show that the set of all merge pairs of size n which have exactly the average number of alternations turns out to be a "representative" of the entire set of merge pairs in the following sense: the average comparison time over all merge pairs, i.e. T_M(n,n), is identical to the time T_M[(n,n)] which merge takes when restricted to merge pairs which have exactly n alternations merge pairs which have exactly the average number of alternations. Finally, we show that the average time,T_M[n,n] = 2n²n+1, can be expressed intuitively as the product of the average number of alternations by the average number of comparisons that occur between alternations.