Tutorial de Merge Sort en Python

Ordenar datos es una de las operaciones más comunes que realizan los profesionales de datos en su trabajo diario. Muchas veces necesitamos mostrar datos en un cierto orden para extraer información significativa. Afortunadamente, hoy en día no tenemos que hacer esta tarea manualmente. Las computadoras pueden hacer la magia por nosotros con un rendimiento imbatible.

Hay varias estrategias para ordenar datos. En este tutorial, analizaremos una de las técnicas de ordenación más efectivas. El algoritmo “merge sort” utiliza una estrategia de divide y vencerás para ordenar un array desordenado dividiéndolo primero en arrays más pequeños, que luego se fusionan en el orden correcto.

En las secciones siguientes, discutiremos todos los detalles del algoritmo merge sort, cómo se ve en Python y algunos consejos prácticos para una implementación fluida.

¿Qué es Merge Sort?

Existen muchos algoritmos de ordenación, pero es difícil encontrar uno que funcione mejor que merge sort. No es sorprendente que este algoritmo se utilice en todo tipo de aplicaciones del mundo real, como ordenar bases de datos grandes o organizar archivos en un ordenador regular.

El algoritmo se basa en el paradigma de divide y vencerás, que se puede dividir en tres partes:

• Dividir: este proceso divide el problema en subproblemas más pequeños.
• Vencer: los subproblemas se resuelven de forma recursiva.
• Combinar: las soluciones de los subproblemas se combinan para lograr la solución final.

Estrategia de divide y vencerás

Veamos cómo funciona el ordenamiento por mezcla. Supongamos que queremos ordenar los siguientes números aplicando el algoritmo de ordenamiento por mezcla. El algoritmo divide los datos recursivamente en dos partes y sigue dividiendo hasta que cada lista tiene un elemento. Luego, los combinamos ordenándolos en otra lista.

Problema de Ordenamiento por Mezcla. Fuente: DataCamp

Complejidad de Tiempo y Espacio del Ordenamiento por Mezcla

Es imposible saber de antemano cuál es el algoritmo de ordenamiento que mejor funciona para un cierto problema. Se deben considerar varias variables más allá del algoritmo, incluyendo el lenguaje de programación utilizado para escribir el código, el hardware en el que se ejecutan y las particularidades de los datos a ordenar.

Aunque no podemos predecir el tiempo de ejecución exacto de un algoritmo de ordenamiento, todavía podemos comparar el rendimiento de varios algoritmos de ordenamiento analizando la complejidad de tiempo y espacio.

Complejidad de tiempo del ordenamiento por mezcla

Como explicamos en una guía separada sobre Notación Big O y Complejidad Temporal, el objetivo del análisis de complejidad temporal no es predecir el tiempo de ejecución exacto de un algoritmo, sino evaluar cuán eficiente es un algoritmo al analizar cómo cambia su tiempo de ejecución a medida que aumenta la cantidad de datos de entrada.

El análisis de complejidad temporal se escribe en notación Big O, una notación matemática que describe la tasa a la que una función crece o disminuye. El ordenamiento por mezcla tiene una complejidad temporal log-lineal o linealítica, notada como O(N log(N)), donde N es el número de elementos en la lista. La letra ‘O’ representa el ‘orden’ de crecimiento.

En el análisis de complejidad temporal, la complejidad linealítica se comporta aproximadamente de manera similar a la complejidad lineal, lo que significa que su ejecución será directamente proporcional a la cantidad de datos. Así, si la cantidad de datos se duplica, el tiempo que tarda el algoritmo en procesar los datos también debería duplicarse, es decir, el número de divisiones y fusiones se duplicará.

Debido a que la complejidad temporal del ordenamiento por mezcla se comporta de manera lineal, su complejidad se mantiene igual en los mejores, promedios y peores casos. Eso significa que, independientemente del orden de entrada, el algoritmo siempre tomará el mismo número de pasos para completarse.

Complejidad espacial del ordenamiento por mezcla

Finalmente, además del tiempo requerido para terminar la tarea, otro aspecto importante al analizar la complejidad del algoritmo es estimar cuánta memoria requerirá el algoritmo para completarse a medida que el problema se hace más grande.

Esto está cubierto por los conceptos de complejidad espacial y espacio auxiliar. Este último se refiere al espacio adicional o espacio temporal utilizado por un algoritmo, mientras que el primero se refiere al espacio total tomado por el algoritmo con respecto al tamaño de la entrada. En otras palabras, la complejidad espacial incluye tanto el espacio auxiliar como el espacio utilizado por la entrada.

El merge sort tiene una complejidad espacial de O(N). Esto se debe a que utiliza un arreglo auxiliar de tamaño N para fusionar las mitades ordenadas del arreglo de entrada. El arreglo auxiliar se utiliza para almacenar el resultado fusionado, y el arreglo de entrada se sobrescribe con el resultado ordenado.

Implementación de Merge Sort en Python

Implementemos el algoritmo de merge sort en Python. Hay varias formas de codificar el algoritmo; sin embargo, nos ceñiremos a la basada en la recursión, que es probablemente la más fácil de entender y requiere menos líneas de código que otras alternativas basadas en la iteración.

Comprensión de la recursión en merge sort

Si eres nuevo en el tema, en programación, la recursión ocurre cuando una función se llama a sí misma. Puedes consultar nuestro Tutorial de Entendimiento de Funciones Recursivas en Python para aprender todo sobre estas poderosas funciones.

Para implementar el merge sort, primero definimos el caso base: si la lista tiene solo un elemento, ya está ordenada, por lo que regresamos inmediatamente. De lo contrario, dividimos la lista en dos mitades, left_half y right_half, y llamamos a merge_sort() recursivamente en cada una de ellas. Este proceso continúa hasta que todas las sublistas contienen un solo elemento.

Una vez que tenemos estas sublistas ordenadas, comenzamos el proceso de fusión. Para hacer esto, inicializamos tres variables de índice: i para seguir la posición en left_half, j para right_half, y k para la lista fusionada final. Luego comparamos elementos de ambas mitades. Si el elemento actual en left_half es más pequeño, lo colocamos en my_list[k] y movemos i hacia adelante. De lo contrario, tomamos el elemento de right_half, lo colocamos en my_list[k], e incrementamos j. Después de cada comparación, movemos k hacia adelante a la siguiente posición en la lista final.

Este proceso continúa hasta que hayamos comparado todos los elementos en una de las mitades. Si quedan elementos en left_half o right_half, los agregamos directamente a la lista final, asegurando que no se pierda ningún dato. Debido a que el merge sort opera de manera recursiva, este proceso de fusión se ejecuta en cada nivel de recursión hasta que toda la lista esté ordenada.

Implementación en Python

A continuación, puedes encontrar el código utilizando la lista no ordenada del diagrama anterior como ejemplo:

def merge_sort(my_list):
    if len(my_list) > 1: 
        mid = len(my_list)//2
        left_half = my_list[:mid]
        right_half = my_list[mid:]
       
        merge_sort(left_half)
        merge_sort(right_half)

        i = j = k = 0
 
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                my_list[k] = left_half[i]                
                i += 1
            else:
                my_list[k] = right_half[j]
                j += 1
            k += 1
     
        while i < len(left_half):
            my_list[k] = left_half[i]
            i += 1
            k += 1
 
        while j < len(right_half):
            my_list[k] = right_half[j]
            j += 1
            k += 1

my_list = [35,22,90,4,50,20,30,40,1]
merge_sort(my_list)
print(my_list)
>>> [1, 4, 20, 22, 30, 35, 40, 50, 90]

Comparación de Merge Sort con Otros Algoritmos de Ordenamiento

Merge sort es un algoritmo de ordenamiento bastante rápido, especialmente adecuado para bases de datos grandes, y a menudo se utiliza como referencia para otros algoritmos. Sin embargo, cuando se trata de listas más cortas, su rendimiento tiende a ser inferior a otros algoritmos de ordenamiento.

En la siguiente tabla, puedes encontrar una comparación de merge sort con otros algoritmos de ordenamiento populares.

Aplicaciones Prácticas del Ordenamiento por Mezcla

El merge sort tiene un alto rendimiento al ordenar listas grandes, pero su eficiencia disminuye al trabajar con listas más pequeñas. Igualmente, tiende a ser menos eficiente en escenarios donde ya existe cierto grado de orden en las listas de entrada, ya que el merge sort realizará los mismos pasos independientemente del orden de la lista.

Un caso de uso ideal donde el merge sort resulta particularmente útil es en listas enlazadas. Una lista enlazada es una estructura de datos que consta de una conexión de nodos enlazados linealmente entre sí. Cada nodo contiene los datos y el enlace para conectarlo con el siguiente nodo.

El merge sort es preferido para listas enlazadas porque solo requiere acceso secuencial a los datos, lo cual se alinea bien con la naturaleza de las listas enlazadas. Además, el merge sort es un algoritmo de ordenación estable (es decir, preserva el orden relativo de elementos iguales en la salida ordenada), lo cual es una consideración muy importante para mantener el orden de las listas enlazadas.

Errores Comunes y Solución de Problemas

El algoritmo merge sort es bastante sencillo y el margen de mejora en el código es limitado. Sin embargo, puedes aumentar la complejidad de tu estrategia de ordenación teniendo en cuenta el tamaño de los datos de entrada. 

Ya hemos establecido que el merge sort funciona mejor con conjuntos de datos más grandes. Para conjuntos de datos más pequeños, otros algoritmos de ordenación con complejidad temporal O(N^2), como el insertion sort, pueden funcionar mejor. En este caso, simplemente necesitarías establecer un umbral de tamaño por debajo del cual optarías por el algoritmo insertion sort en lugar de merge sort.

Otra idea interesante para explorar sería la paralelización. Los pasos del merge sort se pueden paralelizar fácilmente con la potencia informática adecuada, reduciendo así el tiempo de completación. Lee nuestra guía de CPU vs GPU para aprender más sobre la computación paralela. 

Conclusión

El merge sort es uno de los algoritmos de ordenamiento más efectivos y populares, pero hay mucho más por descubrir en el maravilloso y siempre en expansión universo de los algoritmos. Si te interesa la técnica de los algoritmos, cómo funcionan y su complejidad, virtudes y desventajas asociadas, estos recursos de DataCamp pueden ayudarte a continuar tu aprendizaje:

• Curso de Introducción a Estructuras de Datos y Algoritmos
• Track de Habilidades de Programación en Python
• Track de Fundamentos de Datos en Python
• Curso Intermedio de Python
• Track de Carrera de Analista de Datos en Python
• Notación Big O y Complejidad Temporal