Vista general del ordenamiento por mezcla

Como estamos usando divide y vencerás para ordenar, tenemos que decidir cómo se van a ver nuestros subproblemas. El problema completo es ordenar todo un arreglo. Digamos que un subproblema es ordenar un subarreglo. En particular, vamos a pensar que un subproblema es ordenar el subarreglo que empieza en el índice p y va hasta el índice r. Será conveniente tener una notación para un subarreglo, así que digamos que array[p..r] denota este subarreglo de array. Ten en cuenta que esta notación de "dos puntos" no está permitida en JavaScript; la estamos usando para describir el algoritmo, en vez de una implementación particular del algoritmo en código. En términos de nuestra notación, para un arreglo de n elementos, podemos decir que el problema original es ordenar array[0..n-1].
Aquí está cómo el ordenamiento por mezcla utiliza divide y vencerás:
  1. Divide al encontrar el número q de la posición a medio camino entre p y r. Haz este paso de la misma manera en que encontramos el punto medio en la búsqueda binaria: suma p y r, divide entre 2 y redondea hacia abajo.
  2. Vence al ordenar de manera recursiva los subarreglos en cada uno de los dos subproblemas creados por el paso de dividir. Es decir, ordena de manera recursiva el subarreglo array[p..q] y ordena de manera recursiva el subarreglo array[q+1..r].
  3. Combina al mezclar los dos subarreglos ordenados de regreso en un solo subarreglo ordenado array[p..r].
Necesitamos un caso base. El caso base es el subarreglo que contiene menos de dos elementos, es decir, cuando p, is greater than or equal to, r, ya que un subarreglo sin elementos o con solo un elemento ya está ordenado. Así que vamos a dividir-vencer-combinar solo cuando p, is less than, r.
Veamos un ejemplo. Vamos a empezar con array que contiene a [14, 7, 3, 12, 9, 11, 6, 2], de modo que el primer subarreglo es en realidad el arreglo completo, array[0..7] (p, equals, 0 y r, equals, 7). Este subarreglo tiene por lo menos dos elementos, así que no es un caso base.
  • En el paso de dividir, calculamos q, equals, 3.
  • El paso de vencer nos hace ordenar los dos subarreglos array[0..3], que contiene a [14, 7, 3, 12], y array[4..7], que contiene a [9, 11, 6, 2]. Cuando regresamos del paso de vencer, cada uno de los dos subarreglos está ordenado: array[0..3] contiene a [3, 7, 12, 14] y array[4..7] contiene a [2, 6, 9, 11], de modo que el arreglo completo es [3, 7, 12, 14, 2, 6, 9, 11].
  • Por último, el paso de combinar mezcla los dos subarreglos en la primera y la segunda mitad, para producir el arreglo final ordenado [2, 3, 6, 7, 9, 11, 12, 14].
¿Cómo se ordenó el subarreglo array[0..3]? Del mismo modo. Tiene más de dos elementos, así que no es un caso base. Con p, equals, 0 y r, equals, 3, calcula q, equals, 1, ordena recursivamente array[0..1] ([14, 7]) y array[2..3] ([3, 12]), cuyo resultado es array[0..3] que contiene a [7, 14, 3, 12], y mezcla la primera mitad con la segunda mitad, para producir [3, 7, 12, 14].
¿Cómo se ordenó el subarreglo array[0..1]? Con p, equals, 0 y r, equals, 1, calcula q, equals, 0, ordena recursivamente array[0..0] ([14]) y array[1..1] ([7]), cuyo resultado es array[0..1] que sigue conteniendo a [14, 7], y mezcla la primera mitad con la segunda mitad, para producir [7, 14].
Los subarreglos array[0..0] y array[1..1] son casos base, ya que cada uno contiene menos de dos elementos. Aquí está cómo se desarrolla todo el algoritmo del ordenamiento por mezcla:
Ordenamiento por mezcla
La mayoría de los pasos en el ordenamiento por mezcla son sencillos. Puedes revisar el caso base fácilmente. Encontrar el punto medio q en el paso de dividir también es muy fácil. Tienes que hacer dos llamadas recursivas en el paso de vencer. Es en el paso de combinar, en donde tienes que mezclar dos subarreglos ordenados, en donde ocurre el trabajo verdadero. Por el momento, vamos a suponer que sabemos cómo mezclar dos subarreglos ordenados de manera eficiente y vamos a continuar enfocándonos en el ordenamiento por mezcla como un todo.

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.