Dado que la función merge se ejecuta en un tiempo Θ(n) \Theta(n) al mezclar n elementos, ¿cómo llegamos a mostrar que mergeSort se ejecuta en un tiempo Θ(nlgn) \Theta(n \lg n) ? Empezamos por pensar acerca de las tres partes de divide y vencerás y cómo contabilizar sus tiempos de ejecución. Suponemos que estamos ordenando un total de n elementos en todo el arreglo.
  1. El paso de dividir tarda un tiempo constante, sin importar el tamaño del subarreglo. Después de todo, el paso de dividir simplemente calcula el punto medio q de los índices p y r. Recuerda que en la notación Θ grande, indicamos un tiempo constante por Θ(1) \Theta(1) .
  2. El paso de vencer, en donde ordenamos dos subarreglos de aproximadamente n, slash, 2 elementos cada uno, se tarda una cierta cantidad de tiempo, pero vamos a contabilizar ese tiempo cuando consideremos los subproblemas.
  3. El paso de combinar mezcla un total de n elementos y se tarda un tiempo Θ(n) \Theta(n) .
Si pensamos acerca de los pasos de dividir y combinar juntos, el tiempo de ejecución Θ(1) \Theta(1) del paso de dividir es un término de orden inferior comparado con el tiempo de ejecución Θ(n) \Theta(n) del paso de combinar. Así que vamos a pensar en los pasos de dividir y de combinar que juntos tardan un tiempo Θ(n) \Theta(n) . Para hacer las cosas más concretas, vamos a decir que los pasos de dividir y combinar juntos tardan un tiempo c, n para alguna constante c.
Para mantener las cosas relativamente sencillas, vamos a suponer que si n, is greater than, 1, entonces n siempre es par, de modo que cuando tengamos que pensar en n, slash, 2, sea un entero. (Contabilizar para el caso en que n sea impar no cambia el resultado en términos de notación Θ grande). Así que podemos pensar en el tiempo de ejecución de mergeSort sobre un subarreglo de n elementos como la suma de dos veces el tiempo de ejecución de mergeSort sobre un subarreglo de left parenthesis, n, slash, 2, right parenthesis elementos (para el paso de vencer) más c, n (para los pasos de dividir y combinar, en realidad solo para la mezcla).
Ahora tenemos que averiguar el tiempo de ejecución de dos llamadas recursivas sobre n, slash, 2 elementos. Cada una de estas dos llamadas recursivas tarda el doble del tiempo de ejecución de mergeSort sobre un subarreglo de left parenthesis, n, slash, 4, right parenthesis elementos (porque tenemos que dividir n, slash, 2 a la mitad) más c, n, slash, 2 para mezclar. Tenemos dos subproblemas de tamaño n, slash, 2, y cada uno tarda un tiempo c, n, slash, 2 en mezclar, de modo que el tiempo total que tardamos en mezclar los subproblemas de tamaño n, slash, 2 es 2, dot, c, n, slash, 2, equals, c, n.
Vamos a dibujar los tiempos de mezcla en un "árbol":
Primer árbol del ordenamiento por mezcla
Los computólogos dibujan árboles al revés de como crecen los árboles en realidad. Un árbol es un grafo sin ciclos (caminos que empiezan y acaban en el mismo lugar). La convención es llamar los vértices en un árbol sus nodos. El nodo raíz está hasta arriba; aquí, la raíz está etiquetada con el tamaño n del subarreglo para el arreglo original de n elementos. Debajo están los dos nodos secundarios, cada uno etiquetado n, slash, 2 para representar los tamaños de los subarreglos para los dos subproblemas de tamaño n, slash, 2.
Cada uno de los subproblemas de tamaño n, slash, 2 ordena recursivamente los dos subarreglos de tamaño left parenthesis, n, slash, 2, right parenthesis, slash, 2, o n, slash, 4. Como hay dos subproblemas de tamaño n, slash, 2, hay cuatro subproblemas de tamaño n, slash, 4. Cada uno de estos cuatro subproblemas mezcla un total de n, slash, 4 elementos, así que el tiempo de mezcla para cada uno de los cuatro subproblemas es c, n, slash, 4. Sumados sobre los cuatro subproblemas, vemos que el tiempo total de mezcla para los cuatro subproblemas de tamaño n, slash, 4 es 4, dot, c, n, slash, 4, equals, c, n:
Primer árbol del ordenamiento por mezcla
¿Qué crees que pasará con los subproblemas de tamaño n, slash, 8? Habrá ocho de ellos, y el tiempo de mezcla para cada uno será c, n, slash, 8, para un tiempo total de mezcla de 8, dot, c, n, slash, 8, equals, c, n:
Primer árbol del ordenamiento por mezcla
A medida que los subproblemas se hacen más pequeños, el número de subproblemas se duplica en cada "nivel" de la recursión, pero el tiempo de mezcla se divide a la mitad. La duplicación y división a la mitad se cancelan, de modo que el tiempo total de mezcla es c, n en cada nivel de recursión. Eventualmente, llegamos a subproblemas de tamaño 1: el caso base. Tenemos que pasar un tiempo Θ(1) \Theta(1) ordenando subarreglos de tamaño 1, porque tenemos que probar si p, is less than, r, y esta prueba toma tiempo. ¿Cuántos subarreglos de tamaño 1 hay? Como empezamos con n elementos, debe haber n de ellos. Como cada caso base tarda un tiempo Θ(1) \Theta(1) , digamos que en conjunto, los casos base tardan un tiempo c, n:
Primer árbol del ordenamiento por mezcla
Ahora ya sabemos cuánto tiempo tarda la mezcla para el tamaño de cada subproblema. El tiempo total para mergeSort es la suma de los tiempos de mezcla para todos los niveles. Si hay l niveles en el árbol, el tiempo total de mezcla es l, dot, c, n. Entonces ¿qué es l? Empezamos con subproblemas de tamaño n y dividimos a la mitad repetidamente hasta llegar a subproblemas de tamaño 1. Vimos esta característica cuando analizamos la búsqueda binaria, y la respuesta es l=lgn+1 l = \lg n + 1 . Por ejemplo, si n, equals, 8, entonces lgn+1=4 \lg n + 1 = 4 , y efectivamente, el árbol tiene cuatro niveles: n, equals, 8, comma, 4, comma, 2, comma, 1. El tiempo total para mergeSort es entonces cn(lgn+1) cn (\lg n + 1) . Cuando usamos notación Θ grande para describir este tiempo de ejecución, descartamos el término de orden inferior (plus, 1) y el coeficiente constante (c), dándonos un tiempo de ejecución de Θ(nlgn) \Theta(n \lg n) , según lo prometido.
Otra cosa acerca del ordenamiento por mezcla que vale la pena destacar. Durante la mezcla, se hace una copia de todo el arreglo que se está ordenando, con una mitad en lowHalf y la otra mitad en highHalf. Como copia más de un número constante de elementos en algún momento, decimos que el ordenamiento por mezcla no trabaja in situ. En contraste, tanto el ordenamiento por selección como el ordenamiento por inserción sí trabajan in situ, ya que nunca hacen una copia de más de un número constante de elementos del arreglo en cualquier momento. A los computólogos les gusta considerar si un algoritmo trabaja in situ o no, porque hay algunos sistemas en los cuales el espacio es escaso, y por lo tanto son preferibles los algoritmos in situ.

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.