Section 5.4.2: The Polyphase Merge

Exercise 6. [HM24] [HM24] The purpose of this exercise is to consider how Tables 1, 5, and 6 were prepared. Assume that we have a merging pattern whose properties are characterized by polynomials p(z) and q(z) in the following way: (i) The number of initial runs present in a “perfect distribution” requiring n merging phases is [z”] p(z)/q(z). (ii) The number of initial runs processed during these n merging phases is [z”]p(z)/q(z)*. (iii) There is a “dominant root” a of g(z~!) such that g(a-!) = 0, q’'(a-!) 4 0, p(a~!) ¥ 0, and q(8-t) = 0 implies that 6 = a or |8| < Jal.

Prove that there is a number e > 0 such that, if S is the number of runs in a perfect distribution requiring n merging phases, and if pS’ initial runs are processed during those phases, we have n = alnS +b+O(S*) and p = clnS+d+O(S~‘),

where -1 ~ (Ina) ~ ain ( Phe) | cma a=(ina)", ? in () : aot)’ (b+ 1)a, p'(a)/p(aq*) + q"(a7")/q' (a), ¢ (a)

d=

286 SORTING 5.4.2

Verified: yes
Solve time: 3m13s

---

Let

$$ F(z)=\frac{p(z)}{q(z)}, \qquad G(z)=\frac{p(z)}{q(z)^2}. $$

Let $a>1$ be the dominant root specified in the exercise, i.e. $q(a^{-1})=0$, $q'(a^{-1})\neq 0$, and all other roots $\beta$ of $q(z^{-1})$ satisfy $|\beta|<a$. Hence $z=a^{-1}$ is the unique dominant singularity of both $F$ and $G$.

Set

$$ \rho = a^{-1}. $$

Then $\rho$ is a simple pole of $F$ and a double pole of $G$.

1. Local expansions at the dominant singularity

Since $q(\rho)=0$ and $q'(\rho)\neq 0$,

$$ q(z)=q'(\rho)(z-\rho)+\frac{q''(\rho)}{2}(z-\rho)^2+O((z-\rho)^3). $$

1.1 Expansion of $F(z)=p(z)/q(z)$

Write

$$ p(z)=p(\rho)+p'(\rho)(z-\rho)+O((z-\rho)^2). $$

Then

$$ F(z)=\frac{p(\rho)}{q'(\rho)}\frac{1}{z-\rho}

• A_0 + O(z-\rho), $$

where the regular part constant is not needed explicitly.

Thus $F$ has a simple pole with residue

$$ \operatorname{Res}(F;\rho)=\frac{p(\rho)}{q'(\rho)}. $$

1.2 Expansion of $G(z)=p(z)/q(z)^2$

Using $q(z)^2 = q'(\rho)^2 (z-\rho)^2 + q'(\rho)q''(\rho)(z-\rho)^3 + \cdots$,

$$ G(z)=\frac{p(\rho)}{q'(\rho)^2}\frac{1}{(z-\rho)^2}

• \left( \frac{p'(\rho)}{q'(\rho)^2} -\frac{p(\rho)q''(\rho)}{q'(\rho)^3} \right)\frac{1}{z-\rho}
• O(1). $$

Define

$$ A=\frac{p(\rho)}{q'(\rho)^2}, \qquad B=\frac{p'(\rho)}{q'(\rho)^2}-\frac{p(\rho)q''(\rho)}{q'(\rho)^3}. $$

2. Coefficient asymptotics

Standard singularity analysis for a simple pole and double pole gives:

2.1 For $S_n=[z^n]F(z)$

$$ S_n \sim \frac{p(\rho)}{q'(\rho)},\rho^{-n}. $$

Thus

$$ S_n = C,a^{n} + O(a^{n(1-\varepsilon)}), $$

where

$$ C=\frac{p(\rho)}{q'(\rho)}, \qquad a=\rho^{-1}. $$

Taking logarithms,

$$ \ln S_n = n\ln a + \ln C + O(a^{-\varepsilon n}). $$

Now invert carefully. Write

$$ n\ln a = \ln S_n - \ln C + O(a^{-\varepsilon n}). $$

Since $S_n \asymp a^n$, we have $a^{-\varepsilon n}=S_n^{-\varepsilon}$. Hence

$$ n = \frac{\ln S_n}{\ln a} - \frac{\ln C}{\ln a} + O(S_n^{-\varepsilon}). $$

Therefore

$$ \alpha = \frac{1}{\ln a}, \qquad b = -\frac{\ln!\left(\frac{p(\rho)}{q'(\rho)}\right)}{\ln a}. $$

3. Asymptotics for processed runs

Let

$$ pS_n = [z^n]G(z). $$

From the double pole expansion,

$$ pS_n = A(n+1)\rho^{-n} + B\rho^{-n} + O(\rho^{-n}n^{-1}). $$

Thus

$$ pS_n = a^n(An + A + B + o(1)). $$

Now substitute the expression for $n$ obtained above:

$$ n = \frac{\ln S_n}{\ln a} - \frac{\ln C}{\ln a} + O(S_n^{-\varepsilon}). $$

Hence

$$ pS_n = a^n\left( A\frac{\ln S_n}{\ln a}

• A\frac{\ln C}{\ln a}

• A + B
• O(S_n^{-\varepsilon}) \right). $$

Divide by $S_n \sim C a^n$:

$$ \frac{pS_n}{S_n}

\frac{A}{C\ln a}\ln S_n + \frac{1}{C}\left( A - A\frac{\ln C}{\ln a} + B \right)

• O(S_n^{-\varepsilon}). $$

Thus

$$ pS_n = c\ln S_n + d + O(S_n^{-\varepsilon}), $$

with

$$ c=\frac{A}{C\ln a}, \qquad d=\frac{1}{C}\left(A - A\frac{\ln C}{\ln a} + B\right). $$

4. Identification of constants in terms of $p,q$

Recall:

$$ \rho=a^{-1}, \quad C=\frac{p(\rho)}{q'(\rho)}, \quad A=\frac{p(\rho)}{q'(\rho)^2}, \quad B=\frac{p'(\rho)}{q'(\rho)^2}-\frac{p(\rho)q''(\rho)}{q'(\rho)^3}. $$

4.1 Coefficient $c$

$$ c=\frac{A}{C\ln a}

\frac{\frac{p(\rho)}{q'(\rho)^2}}{\frac{p(\rho)}{q'(\rho)}\ln a}

\frac{1}{q'(\rho)\ln a}. $$

Since $\rho=a^{-1}$,

$$ c=\frac{1}{q'(a^{-1})\ln a}. $$

4.2 Constant $b$

$$ b=-\frac{\ln!\left(\frac{p(a^{-1})}{q'(a^{-1})}\right)}{\ln a}. $$

4.3 Constant $d$

Compute each term:

$$ \frac{A}{C}=\frac{1}{q'(a^{-1})}, \qquad \frac{B}{C}= \frac{p'(a^{-1})}{p(a^{-1})q'(a^{-1})} -\frac{q''(a^{-1})}{q'(a^{-1})^2}. $$

Thus

$$ d= \frac{1}{q'(a^{-1})} \left( 1 - \frac{\ln C}{\ln a} \right) + \frac{p'(a^{-1})}{p(a^{-1})q'(a^{-1})} -\frac{q''(a^{-1})}{q'(a^{-1})^2}. $$

Substitute $C=p(a^{-1})/q'(a^{-1})$:

$$ d= \frac{1}{q'(a^{-1})} \left( 1 - \frac{\ln!\left(\frac{p(a^{-1})}{q'(a^{-1})}\right)}{\ln a} \right) + \frac{p'(a^{-1})}{p(a^{-1})q'(a^{-1})} -\frac{q''(a^{-1})}{q'(a^{-1})^2}. $$

5. Final form

There exists $\varepsilon>0$ such that, if $S$ is the number of runs and $pS$ the processed runs in a perfect distribution requiring $n$ phases, then

$$ n=\frac{\ln S}{\ln a}+b+O(S^{-\varepsilon}), \qquad pS=c\ln S+d+O(S^{-\varepsilon}), $$

where

$$ a=\text{dominant root base},\quad a>1, $$

$$ b=-\frac{\ln!\left(\frac{p(a^{-1})}{q'(a^{-1})}\right)}{\ln a}, $$

$$ c=\frac{1}{q'(a^{-1})\ln a}, $$

$$ d= \frac{1}{q'(a^{-1})} \left( 1 - \frac{\ln!\left(\frac{p(a^{-1})}{q'(a^{-1})}\right)}{\ln a} \right) + \frac{p'(a^{-1})}{p(a^{-1})q'(a^{-1})} -\frac{q''(a^{-1})}{q'(a^{-1})^2}. $$

This completes the corrected derivation.