Mezcla en tiempo lineal

La parte restante del ordenamiento por mezcla es la función merge, la cual mezcla dos subarreglos ordenados adyacentes, array[p..q] y array[q+1..r], en un solo subarreglo ordenado en array[p..r]. Vamos a ver cómo construir esta función para que sea lo más eficiente posible. Digamos que los dos subarreglos tienen un total de $n$n elementos. Tenemos que examinar cada uno de los elementos para poder mezclarlos, así que lo mejor que podemos esperar sería un tiempo de mezcla de $\Theta(n)$\Theta, left parenthesis, n, right parenthesis. De hecho, veremos cómo combinar un total de $n$n elementos en un tiempo $\Theta(n)$\Theta, left parenthesis, n, right parenthesis.

Para poder mezclar los subarreglos ordenados array[p..q] y array [q+1..r] y tener el resultado en array[p..r], primero tenemos que hacer arreglos temporales y copiar array[p..q] y array[q+1..r] en estos arreglos temporales. No podemos escribir sobre las posiciones en array[p..r] hasta no tener los elementos que originalmente estaban en array[p..q] y array [q+1..r] copiados de forma segura.

Entonces, lo primero que hay que hacer en la función merge, es asignar dos arreglos temporales, lowHalf y highHalf, para copiar todos los elementos de array[p..q] en lowHalf, y todos los de array[q+1..r] en highHalf. ¿Qué tan grande debe ser lowHalf? El subarreglo array[p..q] contiene $q-p+1$q, minus, p, plus, 1 elementos. ¿Qué hay de highHalf? El subarreglo array[q+1..r] contiene $r-q$r, minus, q elementos. (En JavaScript no tenemos que dar el tamaño de un arreglo cuando lo creamos, pero como sí tenemos que hacerlo en muchos otros lenguajes de programación, a menudo lo consideramos cuando describimos un algoritmo).

En nuestro arreglo de ejemplo, [14, 7, 3, 12, 9, 11, 6, 2], las cosas se ven así después de haber ordenado de manera recursiva array[0..3] y array[4..7] (de modo que $p=0$p, equals, 0, $q=3$q, equals, 3 y $r=7$r, equals, 7) y después de haber copiado estos subarreglos en lowHalf y highHalf:

Los números en array están atenuados para indicar que aunque estas posiciones en el arreglo contienen valores, los valores "reales" están ahora en lowHalf y highHalf. Ahora podemos volver a escribir los números atenuados a voluntad.

A continuación, mezclamos los dos subarreglos ordenados, que ahora están en lowHalf y highHalf, de regreso en array[p..r]. Deberíamos poner el valor más pequeño en cualquiera de los dos subarreglos en array[p]. ¿Dónde podría estar este valor más pequeño? Como los subarreglos están ordenados, el valor más pequeño debe estar en uno de dos lugares: en lowHalf[0] o en highHalf[0] (es posible que el mismo valor esté en ambos lados, y entonces podemos llamar a cualquiera de los dos el valor más pequeño). Con solo una comparación podemos determinar si copiar lowHalf[0] o highHalf[0] en array[p]. En nuestro ejemplo, highHalf[0] fue más pequeño. También vamos a establecer tres variables para indexar los arreglos:

Después de que copiamos de lowHalf o de highHalf a array, debemos incrementar (sumarle 1 a) k de modo que copiemos el siguiente elemento más pequeño en la siguiente posición de array. También tenemos que incrementar i si copiamos de lowHalf, o incrementar j si copiamos de highHalf. Así que aquí están los arreglos antes y después de que el primer elemento se copie de regreso en array:

Atenuamos highHalf[0] para indicar que ya no contiene ningún valor que vamos a considerar. La parte no mezclada del arreglo highHalf empieza en el índice j, que ahora es 1. El valor en array[p] ya no está atenuado porque le copiamos un valor "real".

¿En dónde debe estar el siguiente valor que vamos a copiar de regreso en array? Es el primer elemento no tomado en lowHalf (lowHalf[0]) o el primer elemento no tomado de highHalf (highHalf[1]). Con una comparación, determinamos que lowHalf[0] es más pequeño, así que lo copiamos a array[k] e incrementamos k e i:

A continuación, comparamos lowHalf[1] y highHalf[1], y determinamos que debemos copiar highHalf[1] a array[k]. Después incrementamos k y j:

Seguimos adelante, siempre comparando lowHalf[i] y highHalf[j], copiando el más pequeño de los dos en array[k], e incrementando o i o j:

Eventualmente, todo lowHalf o todo highHalf se copia de regreso en array. En este ejemplo, todo highHalf se copia de regreso antes que los últimos elementos de lowHalf. Terminamos por copiar los elementos restantes no tomados de lowHalf o de highHalf:

Afirmamos que mezclar $n$n elementos tarda un tiempo $\Theta(n)$\Theta, left parenthesis, n, right parenthesis y, por lo tanto, el tiempo de ejecución de mezclar es lineal en el tamaño del subarreglo. Vamos a ver por qué esto es cierto. Vimos tres partes para mezclar:

¿Cuántas líneas de código necesitamos para ejecutar cada uno de estos pasos? Es un número constante por elemento. Cada elemento se copia de array a lowHalf o a highHalf exactamente una vez en el paso 1. Cada comparación en el paso 2 toma un tiempo constante, ya que solo compara dos elementos, y cada elemento "gana" una comparación a lo más una vez. Cada elemento se copia de regreso en array exactamente una vez en los pasos 2 y 3, combinados. Como ejecutamos cada línea de código un número constante de veces por elemento y suponemos que el subarreglo array[p..q] contiene $n$n elementos, el tiempo de ejecución para la mezcla es en efecto $\Theta(n)$\Theta, left parenthesis, n, right parenthesis.

En el siguiente desafío, vas a implementar esta operación de mezclado en tiempo lineal. Con los dos desafíos combinados, habrás implementado completamente el algoritmo de ordenamiento por mezcla.

Este contenido es una colaboración de los profesores de Dartmouth Computer Science Thomas Cormen y Devin Balkcom, con el equipo de contenidos de computación de Khan Academy. El contenido está bajo licencia CC-BY-NC-SA.