Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.