1
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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$.

$\endgroup$
3
  • $\begingroup$ 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 $\endgroup$
    – user25933
    Aug 24, 2012 at 20:02
  • $\begingroup$ 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! $\endgroup$
    – user25933
    Aug 24, 2012 at 20:02
  • $\begingroup$ [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? $\endgroup$
    – user25936
    Aug 24, 2012 at 22:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.