1. ¿Qué es Merge Sort?
Merge Sort es un algoritmo de ordenación dividir y vencerás que sigue un enfoque
recursivo para ordenar una lista o arreglo. Fue propuesto por el matemático John von
Neumann en 1945. El algoritmo funciona dividiendo repetidamente la lista en dos mitades,
ordenando esas mitades de forma recursiva y luego combinando (mezclando) las mitades
ordenadas para obtener la lista final ordenada.
2. Conceptos Clave
Dividir y Vencerás: El principio central de Merge Sort es dividir el problema en
subproblemas más pequeños, resolver esos subproblemas (en este caso, ordenar las
sublistas) y luego combinar los resultados para obtener la solución del problema original.
Recursividad: El algoritmo utiliza recursión para dividir la lista y ordenar cada parte.
Mezcla: Después de que las sublistas están ordenadas, se "mezclan" para formar una
lista ordenada.
3. Procedimiento del Merge Sort
El algoritmo de Merge Sort sigue estos pasos:
División:
Si el arreglo tiene más de un elemento, lo divides en dos mitades.
Cada mitad se ordena de forma recursiva usando el mismo algoritmo.
Conquista (mezcla o fusión):
Una vez que ambas mitades estén ordenadas, se combinan (mezclan) de forma
ordenada.
El proceso de fusión se hace comparando los primeros elementos de ambas mitades y
colocando el más pequeño de los dos en el arreglo resultante.
Recursividad:
El proceso de dividir y fusionar se repite recursivamente hasta que todas las sublistas
contengan solo un elemento, momento en el cual las sublistas ya están ordenadas por sí
solas.
Luego se empieza a fusionar esas sublistas ordenadas para obtener el arreglo final
ordenado.
4. Ejemplo de Merge Sort
Supongamos que tenemos el siguiente arreglo desordenado:
csharp
[38, 27, 43, 3, 9, 82, 10]
Dividir el arreglo hasta que cada sublista tenga un solo elemento:
[38, 27, 43, 3, 9, 82, 10] → divide en [38, 27, 43] y [3, 9, 82, 10]
[38, 27, 43] → divide en [38] y [27, 43]
[3, 9, 82, 10] → divide en [3, 9] y [82, 10]
Y así sucesivamente hasta que tenemos sublistas de un solo elemento.
Fusionar las sublistas:
[38] y [27, 43] se fusionan en [27, 38, 43]
[3, 9] y [82, 10] se fusionan en [3, 9, 10, 82]
Ahora, fusionamos [27, 38, 43] y [3, 9, 10, 82] en un único arreglo ordenado:
[3, 9, 10, 27, 38, 43, 82]
5. Complejidad de Merge Sort
Tiempo de ejecución:
Merge Sort tiene una complejidad temporal de O(n log n) en el peor caso, el mejor caso y
el caso promedio. Esto lo convierte en uno de los algoritmos de ordenación más eficientes
en términos de tiempo para listas grandes, comparado con algoritmos como el bubble sort
o el insertion sort (que tienen O(n²)).
Espacio:
La complejidad espacial de Merge Sort es O(n), ya que necesita espacio adicional para
almacenar las sublistas mientras las fusiona.
6. Características de Merge Sort
Estable: Merge Sort es un algoritmo estable, lo que significa que si hay elementos con el
mismo valor en el arreglo original, su orden relativo se mantiene después de la
ordenación.
No In-place: A diferencia de otros algoritmos como Quick Sort o Heap Sort, Merge Sort no
ordena el arreglo in-place (es decir, no ordena los elementos sin utilizar espacio
adicional). Necesita espacio adicional para la mezcla de sublistas.
Recursivo: Aunque puede implementarse de forma iterativa, Merge Sort suele
implementarse de forma recursiva, lo que puede hacer que sea más fácil de entender y de
escribir.
7. Comparación con otros algoritmos de ordenación
Quick Sort:
Quick Sort, en el peor de los casos, tiene una complejidad O(n²), aunque en promedio se
comporta como O(n log n). Merge Sort tiene una complejidad más predecible (O(n log n))
en todos los casos.
Quick Sort puede ser más rápido que Merge Sort en la práctica debido a su menor uso de
memoria y menor cantidad de movimientos de elementos.
Heap Sort:
Heap Sort también tiene una complejidad O(n log n), pero es menos eficiente en la
práctica que Merge Sort en términos de tiempo, especialmente debido a su acceso no
secuencial a los datos.
Bubble Sort / Insertion Sort:
Estos algoritmos son mucho más lentos, con una complejidad O(n²) en el peor caso. Son
adecuados solo para listas muy pequeñas o casi ordenadas.
