Unir dos listas ordenadas

¿Cuántas comparaciones se necesitan para unir dos listas ordenadas, de largo $n$ y $m$, con $m<n$? Una cota inferior está dada por el número de formas en que los elementos de una lista se pueden insertar en la otra, $\log_2 { m+n \choose m}$. Esto ocurre porque todo algoritmo que haga la unión debe realizar acciones distintas para cada una de las ${ m+n \choose m}$ formas en que puede presentarse el input, y por lo tanto las respuestas a sus comparaciones pueden usarse para codificar ese aspecto del input.

Note que, si $p \ge q$,

$${p \choose q} ~~=~~ \prod_{i=0}^{q-1} \frac{p-i}{q-i} ~~\ge~~ \prod_{i=0}^{q-1} \frac{p}{q} ~~=~~ \left( \frac{p}{q} \right)^q$$

debido a que $\frac{p-i}{q-i} \ge \frac{p}{q}$ pues $(p-i)q = pq - iq \ge pq - ip = p(q-i)$. De esto obtenemos la cota inferior $\log_2 { m+n \choose m} \ge \log_2 ((\frac{m+n}{m})^m) = m\log_2(1+\frac{n}{m})$.

Asintóticamente, esta cota inferior es $\Omega(m\log\frac{n}{m})$ si $m = o(n)$ y $\Omega(m)$ si no. Un algoritmo que alcanza esta cota inferior asintótica es el que toma la lista más corta y avanza en la más larga buscándolo mediante búsqueda exponencial (es decir, comparando el elemento en las posiciones 1, 2, 4, $\ldots$ hacia adelante hasta pasarse y luego completando con búsqueda binaria). Para cada elemento $x_i$ de la lista más corta, sea $y_i$ el primer elemento $\ge x_i$ de la lista más larga. Si la distancia entre $y_i$ e $y_{i-1}$ es de $d_i$ posiciones (en la lista más larga), entonces el costo total será $O(\sum_i \log d_i)$.

Como $\sum_i d_i \le n$, el peor caso se da cuando son todos $d_i = \frac{n}{m}$ (por la desigualdad de Jensen), en cuyo caso el algoritmo toma tiempo $O(m(1+\log\frac{n}{m}))$.

Cuando $m=n$, la cota inferior es $\log_2 { 2n \choose n} \ge 2n - O(\log n)$ (por la aproximación de Stirling), cuyo término principal exacto se alcanza con el método típico de recorrer ambas listas secuencialmente e ir tomando el menor ($2n-1$ comparaciones).