Hoy vamos a ver cómo implementar el ordenamiento por mezcla o merge sort en Python. Básicamente este algoritmo nos va a servir para ordenar un arreglo de cualquier tipo (suponiendo que los valores son comparables).

Hay varios enfoques para este algoritmo; algunos usan una función y otros usan 2. Yo usaré éste último enfoque pues todo queda más claro.

Por cierto, también usaremos la recursividad, ya que es un aspecto clave al momento de ordenar un array con merge sort en Python.

Explicación del algoritmo

Para el ordenamiento por mezcla necesitamos dividir el arreglo en 2, y luego esas 2 partes dividirlas de nuevo en 2. Así hasta tener un par de arreglos de longitud 1 o 0.

Eso que expliqué anteriormente usará la recursividad, ya que la función se va a seguir invocando hasta que la condición de salida se cumpla. Y para este punto ya tendremos un arreglo de 1 o 0.

Ahora viene la segunda parte. Cuando ya tenemos los dos arreglos, los recorremos a ambos con dos índices y vamos agregando el valor menor a un nuevo arreglo, mismo que ya va a estar ordenado.

Cuando ya esté ordenado, lo regresamos. Y este paso se va a repetir por cada par de arreglos. Al final, después de ordenar todas las mitades, el arreglo estará ordenado.

Merge sort en Python

Veamos entonces la primera función. La misma podría llamarse simplemente “dividir” pero la he llamado “merge_sort” para que el nombre tenga sentido al invocarla:

See the gist on github.

En la línea 2 calculamos la longitud del arreglo, ya que vamos a dividirlo según la misma. Luego en la línea 5 tenemos la condición de salida, que es en donde la recursión termina.

Si el arreglo no mide 1 o menos de 1, entonces lo dividimos en dos partes usando operaciones de listas con Python en las líneas 7 y 8.

La recursión está en la línea 9 y 10, que es en donde invocamos a la función dentro de sí misma. Y finalmente en la línea 11 regresamos lo que devuelva merge, que va a combinar el arreglo.

Función merge para ordenar arreglo en Python

Ahora veamos la otra función que va a ordenar ambos arreglos y combinarlos en uno solo.

Aquí es en donde realmente se hace el ordenamiento por merge sort, pues recibimos ambas mitades y las ordenamos en un nuevo arreglo.

See the gist on github.

En la línea 3 iniciamos el arreglo que ya estará ordenado. Aquí vamos a combinar ambas mitades, y al combinarlas vamos a ordenarlas.

Luego en la línea 4, 5 y 6 declaramos los índices.

Por cierto, el índice del arreglo ordenado no importa ya que vamos a usar append y simplemente agregaremos elementos al arreglo ordenado; si estuviéramos en otro lenguaje tal vez sí lo usaríamos.

Luego recorremos ambas mitades en la línea 8, y comparamos en la 11 y dependiendo del arreglo del cual hayamos tomado el elemento aumentamos su índice correspondiente.

Al llenar a la línea 28 puede que hayamos llegado al final de alguna de las mitades, pero no de ambas; entonces simplemente agregamos los elementos restantes de ambas a la lista ordenada.

Finalmente regresamos el arreglo ordenado. Y así tenemos el merge sort aplicado a una lista de Python.

Nota: yo estoy imprimiendo información para que el algoritmo sea más explicativo, tú puedes remover esas líneas sin problema.

Poniendo todo junto

Ahora veamos el código de ambas funciones y el modo de uso. Ya te dije anteriormente que se puede usar un arreglo de cualquier tipo; solo debes hacer la comparación necesaria. El código queda así:

See the gist on github.

Al ejecutarlo, la salida es correcta:

Además, se está imprimiendo información para que veas cómo se separa y ordena el arreglo. Por cierto, el mismo es el que aparece como ejemplo en la Wikipedia.

Para terminar te dejo con otros algoritmos de ordenamiento y más tutoriales de Python.