Mergesort

El algoritmo Mergesort (Ordenamiento por mezcla) es un algoritmo estable y óptimo basado en la técnica divide y vencerás.

Un merge es una operación que combina dos arreglos ordenados en un tercer arreglo ordenado. Por ejemplo, teniendo dos arreglos ordenados 1, 4, 6, 10 y 2, 3, 5, 9 los combinamos y obtenemos el tercer arreglo ordenado 1, 2, 3, 4, 5, 6, 9, 10.

Esta combinación o mezcla es la clave del algoritmo Mergesort.

Análisis

Veámos como se combinan dos secuencias ordenadas utilizando el siguiente arreglo.

Comencemos dividiendo el arreglo a ordenar en dos arreglos ordenados como se muestra a continuación.

Vemos como los dos arreglos están ordenados, por lo que ahora los podemos combinar o mezclar.

Tomamos el primer elemento de los dos arreglos y los comparamos (10 y 5). Al ser menor 5 que 10 lo copiamos en el tercer arreglo.

Recorremos el segundo arreglo y ahora comparamos los valores 10 y 15. Copiamos el 10 por ser el menor.

Recorremos el primer arreglo y ahora comparamos los valores 23 y 15. Copiamos el 15 por ser menor.

Nuevamente recorremos el segundo arreglo y comparamos los valores 23 y 55. Copiamos el 23 por ser el menor.

Una vez más recorremos el primer arreglo y comparamos los valores 30 y 55. Nuevamente copiamos el menor.

Nuevamente recorremos el primer arreglo y comparamos 50 y 55. Bajamos el 50 por ser el menor.

Ya hemos copiado todos los elementos del primer arreglo, por lo que solo queda copiar los elementos restantes del segundo arreglo.

Esta combinación o mezcla es la clave de este algoritmo. No obstante, las mitades deben ordenarse primero. Para lograr esto, el algoritmo se basa en la estrategia divide y vencerás, por lo que implementa una función recursiva hasta dividir todo el arreglo en un solo elemento.