On bounding the average cost of top-down merge sort - MathOverflow

On bounding the average cost of top-down merge sort

2012-08-23T15:14:40Z

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?

Answer by Douglas Zare for On bounding the average cost of top-down merge sort

2012-08-23T23:10:36Z

Inductively, if $A_p \le p \log_2 p + \alpha p + \beta$, then

$A_{2p} \le ((2p) \log_2 (2p) + \alpha (2p) + \beta) + (\beta -2 + \frac {2}{p+1})$

so we'll want $\beta-2 + \frac{2}{p+1} \le 0.$

The odd case is a little harder. Assume the inequality is true for $A_p,A_{p+1}.$

$A_{2p+1} = A_p + A_{p+1} + 2p - 1 + \frac{2}{p+2}$

$ \le (p+1)\log_2 (p+1) + p ~\log_2 p + \alpha(2p+1) + \beta + \beta + 2p - 1 + \frac{2}{p+2}.$

Using $\log_2 x \le \frac{(x-(p+1/2))}{(p+1/2)\log 2} + \log_2 (p+1/2)$ at $x=p, p+1$:

$$A_{2p+1} \le (p+1)\log_2 (p+1/2) + p~\log_2p + \frac{p+1}{(2p+1)\log 2} - \frac {p}{(2p+1)\log 2} \\ + \alpha(2p+1) + \beta + \beta + 2p - 1 + \frac{2}{p+2}$$

$$A_{2p+1} \le \bigg((2p+1)\log_2(2p+1) + \alpha(2p+1) + \beta \bigg) + \\ \beta -2+ \frac{2}{p+2}+\frac{1}{(2p+1)\log 2}.$$

So, we'll also want $\beta - 2 + \frac{2}{p+2} + \frac{1}{(2p+1)\log 2} \le 0.$ Then if we choose $\alpha, \beta$ so that the base of the induction is satisfied, we get $A_n \le n \log_2 n + \alpha n + \beta.$

I think that you can get slightly better bounds by starting the induction higher, but let's start it at $p=1, A_2 = 1, A_3 = \frac 8 3.$ Then we want $4$ inequalities to be satisfied:

$1 \le 2 \log_2 2 + 2\alpha + \beta$

$\frac 8 3 \le 3 \log_2 3 + 3\alpha + \beta$

$\beta -2 + 1 \le 0$

$\beta -2 + \frac 23 + \frac{1}{3 \log 2} \le 0$

and we want to minimize $\alpha$ and then minimize $\beta$ for that $\alpha$ subject to these constraints. If I calculate correctly, then the solution is $\alpha = -\frac76 + \frac{1}{6 \log 2} = -0.9263, \beta = \frac43 - \frac 1{3\log 2} = 0.8524,$ and $A_n \le n \log_2 n + \alpha n + \beta$ should be satisfied for all $n \ge 2$. You can get a slightly lower value of $\alpha$ if you don't need the formula to work for $n=2$.

Answer by Christian for On bounding the average cost of top-down merge sort

2012-08-24T20:02:26Z

Douglas,

Thank you very much for this elegant and didactic derivation. This is what I was hoping for.

I just have a few remarks.

The inequality on $\beta$ obtained from bounding $A_{2p+1}$ always implies the inequality obtained from $A_{2p}$, so we can get rid of the latter; in particular, we don't need the third inequality when setting $p=1$ at the end.

When $p=1$, the two first inequalities show that if we want to minimize $\alpha$, we can maximize $\beta \geq 0$, and we know the upper bound on $\beta$ to be the value you provide. Then, the second inequality (again the odd case) yields the lowest value for $\alpha$, that is, $\alpha = \frac{4}{9} - \lg 3 + \frac{1}{9\ln 2} \simeq -0.9802$.

The advanced analytical techniques I alluded to yield $A_n = n\lg n - (1.25 \pm 0.01)n + O(1)$.

I will work out the lower bound following your inductive method. Thanks again!

Answer by Christian for On bounding the average cost of top-down merge sort

2012-08-24T22:25:44Z

[I can't edit my answer.] Douglas is right, of course: when you have two lower bounds, you can only take the largest, so the even case rules for deciding $\alpha$, which is indeed the value given by Douglas. Sorry about that.

Perhaps a better upper bound on $\lg p$ and $\lg(p+1)$ in terms of $\lg(2p+1)$ would yield a better result?