Let $A_n$ be the average number of comparisons to sort $n$ keys by merging them in a top-down fashion (see any algorithm textbook). It can he shown that $$ A_0 = A_1 = 0;\quad A_n = A_{\lfloor{n/2}\rfloor} + A_{\lceil{n/2}\rceil} + n - \frac{\lfloor{n/2}\rfloor}{\lceil{n/2}\rceil+1} - \frac{\lceil{n/2}\rceil}{\lfloor{n/2}\rfloor+1}. $$ (See Knuth's AOCP, for instance.)
Flajolet and Golin in 1993 used complex analysis (Mellin transforms) and Fourier analysis to find a precise asymptotic approximation of $A_n$. I am interested in finding lower and upper bounds on $A_n$ of the form $n\lg n + \alpha n + \beta$, where $\lg n$ is the binary logarithm, not using these powerful but complicated analytical approaches.
By distinguishing on the parity of $n$, we simply get $$ A_{2p} = 2 A_{p} + 2p - 2 + \frac{2}{p+1};\quad A_{2p+1} = A_{p} + A_{p+1} + 2p - 1 + \frac{2}{p+2}. $$ I tried difference equations, by letting $\Delta_n := A_{n+1} - A_{n}$, yielding $$ \Delta_{2p} = \Delta_{p} + 1 + \frac{2}{p+2} - \frac{2}{p+1};\quad \Delta_{2p+1} = \Delta_p + 1. $$ Then, I am stuck.
The same study for the maximum number of comparisons leads to simpler difference equations: $\Delta_{2p} = \Delta_{2p+1} = \Delta_{p} + 1$, which implies $\Delta_n = \lfloor{\lg n}\rfloor + 1$, to wit, the number of bits in the binary expansion of $n$. From there, a closed form for the maximum cost $\sum_{k=1}^{n-1}\Delta_k$ follows relatively easily (see Flajolet and Sedgewick, for instance).
Any idea how to bound $\Delta_k$ and $\sum_{k=1}^{n-1}\Delta_k$ in the present case?
