Ordenamiento

Extenderemos el algoritmo de MergeSort a memoria secundaria. MergeSort comienza dividiendo el arreglo en dos y se invoca recursivamente, hasta que los subarreglos que tiene que ordenar son de tamaño 1. Entonces vuelve de la recursión, uniendo los subarreglos ordenados derecho e izquierdo en forma ordenada.

En un entorno de memoria secundaria, tiene sentido detener esta recursión cuando los subarreglos a ordenar son de tamaño $B$. En este momento se puede leer el bloque de disco, ordenarlo, y reescribirlo a costo $O(1)$ en I/Os. A la vuelta de la recursión, la unión se hace leyendo secuencialmente los dos subarreglos, usando un buffer de tamaño $B$ en memoria para cada subarreglo y otro para el resultado del merging. En total, todas las uniones de un nivel del árbol requieren leer el arreglo completo y reescribirlo, a costo $O(\frac{N}{B}) = O(n)$. Como la recursión se detiene en los subarreglos de tamaño $B$, la cantidad de niveles en la recursión es $\log_2 \frac{N}{B}$. Es decir, esta variante de MergeSort requiere $O(\frac{N}{B}\log\frac{N}{B}) = O(n\log n)$ I/Os.

Podemos mejorar este costo deteniendo la recursión cuando el subarreglo a ordenar es de tamaño $M$. En este punto, simplemente se lee el subarreglo a memoria, se ordena (gratis), y se reescribe ordenado. Con la reducción resultante de la cantidad de niveles, el costo de ordenar pasa a ser $O(\frac{N}{B}\log\frac{N}{M}) = O(n\log \frac{n}{m})$ I/Os.

Se consigue una reducción adicional mediante aumentar la aridad del árbol de recursión, es decir, no particionando el subarreglo en dos sino en más. El único límite a la aridad del árbol de la recursión es que, al unir, se necesita tener un buffer de $B$ elementos en memoria por cada archivo que se une, por lo cual éstos no pueden exceder $\frac{M}{B}-1$. Ahora la cantidad de niveles es $O(\log_\frac{M}{B} \frac{N}{M})$, por lo que la cantidad de I/Os del algoritmo se reduce a $O(\frac{N}{B}\log_\frac{M}{B} \frac{N}{M}) = O(n\log_m \frac{n}{m}) = O(n\log_m n)$ (notar que las últimas dos expresiones difieren sólo en $O(n)$, que es un término de orden inferior).

Esta complejidad es bastante buena en la práctica. Considerando una memoria de GBs y un bloque de KBs, se pueden ordenar PBs (petabytes, $2^{50}$) con sólo dos pasadas de lectura y dos de escritura sobre los datos. En la práctica, sin embargo, cuando se usan discos magnéticos, puede ser mala idea llegar realmente a la aridad $\frac{M}{B}-1$, pues esto aumenta la cantidad de seeks a posiciones aleatorias para leer bloques de muchos archivos distintos. Experimentalmente el óptimo suele ser unir de a unas decenas de archivos por vez. En este caso, ordenar unos PBs puede requerir unas 10 lecturas y escrituras del arreglo completo.

Note que, con la estructura adecuada para la unión, el costo de CPU de este algoritmo es $O(N\log N)$. Cuando se hace la unión de $\frac{M}{B}-1$ archivos, debe usarse una cola de prioridad en memoria principal para extraer el mínimo entre los primeros elementos de cada uno de los $\frac{M}{B}-1$ buffers. Eso hace que el costo de unir todos los datos de un nivel sea $O(N\log m)$. Multiplicado por los $\log_m \frac{N}{M}$ niveles, nos da $O(N\log\frac{N}{M})$. A esto debe agregarse el costo de CPU de ordenar los $\frac{N}{M}$ subarreglos de largo $M$ en memoria, en el último nivel de la recursión, $O(N\log M)$, lo que en total nos da $O(N\log N)$.

📄️ Cota Inferior

Demostraremos que este algoritmo de ordenamiento es óptimo si se procede por