Tutorial Python de Ordenación por Fusión

Ordenar datos es una de las operaciones más habituales que realizan los profesionales de los datos en su trabajo diario. Muchas veces necesitamos mostrar los datos en un orden determinado para extraer información significativa. Por suerte, hoy en día no tenemos que hacer esta tarea manualmente. Los ordenadores pueden hacer la magia por nosotros con un rendimiento insuperable.

Hay varias estrategias para ordenar los datos. En este tutorial, analizaremos una de las técnicas de clasificación más eficaces. El algoritmo de "ordenación por fusión" utiliza una estrategia de divide y vencerás para ordenar una matriz sin ordenar, dividiéndola primero en matrices más pequeñas, que luego se fusionan en el orden correcto. 

En las próximas secciones, hablaremos de todos los detalles del algoritmo de ordenación por fusión, de su aspecto en Python y de algunos consejos prácticos para aplicarlo sin problemas.

¿Qué es la Ordenación por Fusión?

Existen muchos algoritmos de ordenación, pero es difícil encontrar uno que funcione mejor que la ordenación combinada. Como es lógico, este algoritmo se utiliza en todo tipo de aplicaciones del mundo real, como ordenar grandes bases de datos u organizar archivos en un ordenador normal.

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

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

Estrategia de divide y vencerás

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

Problema de ordenación combinada. Fuente: DataCamp

Complejidad temporal y espacial de la ordenación combinada

Es imposible saber de antemano cuál es el algoritmo de ordenación que mejor funciona para un determinado problema. Hay que tener en cuenta varias variables más allá del algoritmo, como el lenguaje de programación utilizado para escribir el código, el hardware en el que se ejecutan y las particularidades de los datos que hay que ordenar. 

Aunque no podamos predecir el tiempo de ejecución exacto de un algoritmo de ordenación, podemos comparar el rendimiento de varios algoritmos de ordenación analizando la complejidad temporal y espacial.

Complejidad temporal de la ordenación por fusión

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

El análisis de la complejidad temporal se escribe en notación Big O, una notación matemática que describe la velocidad a la que crece o decrece una función. La ordenación por fusión tiene una complejidad de tiempo logarítmica-lineal o lineal-rítmica, indicada como O(N log(N)), donde N es el número de elementos de la lista. La letra "O" representa el "orden" del crecimiento. 

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

Como la complejidad temporal de la ordenación por fusión se comporta linealmente, su complejidad sigue siendo la misma para los casos mejor, medio y peor. Esto significa que, independientemente del orden de entrada, el algoritmo siempre tardará el mismo número de pasos en completarse.

Complejidad espacial de la ordenación por fusión

Por último, además del tiempo necesario para terminar la tarea, otro aspecto importante al analizar la complejidad de un algoritmo es estimar cuánta memoria necesitará el algoritmo para completarse a medida que el problema sea mayor. 

De ello se ocupan los conceptos de complejidad espacial y espacio auxiliar. Este último se refiere al espacio extra o temporal que utiliza un algoritmo, mientras que el primero se refiere al espacio total que ocupa el algoritmo con respecto al tamaño de entrada. En otras palabras, la complejidad espacial incluye tanto el espacio auxiliar como el espacio utilizado por la entrada.

La ordenación por combinación tiene una complejidad espacial de O(N). Esto se debe a que utiliza una matriz auxiliar de tamaño N para unir las mitades ordenadas de la matriz de entrada. La matriz auxiliar se utiliza para almacenar el resultado combinado, y la matriz de entrada se sobrescribe con el resultado ordenado.

Ordenación por combinación en Python

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

Comprender la recursividad en la ordenación por combinación

Si eres nuevo en el tema, en programación, la recursividad se produce cuando una función se llama a sí misma. Puedes consultar nuestro tutorial Comprender las funciones recursivas en Python para aprenderlo todo sobre estas potentes funciones.

Para aplicar la ordenación por fusión, primero definimos el caso base: si la lista sólo tiene un elemento, ya está ordenada, así que volvemos inmediatamente. En caso contrario, dividimos la lista en dos mitades, left_half y right_half, y llamamos recursivamente a merge_sort() en cada una de ellas. Este proceso continúa hasta que todas las sublistas contienen un único elemento.

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

Este proceso continúa hasta que hayamos comparado todos los elementos de una de las mitades. Si queda algún elemento en left_half o right_half, lo añadimos directamente a la lista final, asegurándonos de que no queda ningún dato. Como la ordenación por fusión funciona de forma recursiva, este proceso de fusión se ejecuta en cada nivel de recursión hasta que toda la lista está ordenada.

Implementación de Python

A continuación, encontrarás el código utilizando como ejemplo la lista sin ordenar del diagrama anterior:

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]

Ordenación por combinación frente a otros algoritmos de ordenación

La ordenación por combinación es un algoritmo de ordenación bastante rápido, especialmente adecuado para grandes bases de datos, 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 al de otros algoritmos de ordenación.

En la siguiente tabla, puedes encontrar una comparación de la ordenación por fusión con otros algoritmos de ordenación populares.

Aplicaciones prácticas de la ordenación por combinación

La ordenación por combinación tiene un alto rendimiento cuando se ordenan listas grandes, pero su eficacia disminuye cuando se trabaja con listas más pequeñas. Del mismo modo, tiende a ser menos eficaz en situaciones en las que ya existe cierto grado u orden en las listas de entrada, ya que la ordenación por fusión realizará los mismos pasos sin importar el orden de la lista.

Un gran caso de uso en el que la ordenación por fusión resulta especialmente útil es el de las listas enlazadas. Una lista enlazada es una estructura de datos que comprende una conexión de nodos enlazados linealmente entre sí. Cada nodo contiene los datos y el enlace para conectarlo con el nodo siguiente.

La ordenación por combinación es preferible para las listas enlazadas porque sólo requiere un acceso secuencial a los datos, lo que se ajusta bien a la naturaleza de las listas enlazadas. Además, la ordenación por fusión es un algoritmo de ordenación estable (es decir, conserva el orden relativo de los elementos iguales en la salida ordenada), que es una consideración muy importante para mantener el orden de las listas enlazadas.

Errores comunes y solución de problemas

El algoritmo de ordenación por fusión es bastante sencillo, y el margen de mejora del 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 la ordenación por fusión funciona mejor con conjuntos de datos grandes. Para conjuntos de datos más pequeños, otros algoritmos de ordenación con complejidad temporal O(N^2), como la ordenación por inserción, funcionan mejor. En este caso, sólo tendrías que crear un umbral de tamaño por debajo del cual optarías por el algoritmo de ordenación por inserción en lugar de por el de fusión y ordenación.

Aparte de eso, una buena idea a explorar sería la paralelización. Los pasos de la ordenación por fusión pueden paralelizarse fácilmente con la potencia de cálculo adecuada, reduciendo así el tiempo necesario para completarla. Lee nuestra guía CPU vs GPU para saber más sobre computación paralela. 

Conclusión

La ordenación por combinación es uno de los algoritmos de ordenación más eficaces y populares que existen, pero hay mucho más que aprender en el maravilloso y siempre creciente universo de los algoritmos. Si te interesan los aspectos técnicos de los algoritmos, cómo funcionan y su complejidad, virtudes e inconvenientes asociados, estos recursos de DataCamp pueden ayudarte a continuar tu aprendizaje:

• Curso de Introducción a las Estructuras de Datos y Algoritmos 
• Habilidades de programación en Python
• Curso de Fundamentos de Datos en Python
• Curso de Python Intermedio
• Carrera de Analista de Datos en Python 
• Notación Big O y complejidad temporal