Merge Sort es un algoritmo de ordenamiento clásico que aplica divide y vencerás: divide el arreglo por la mitad, ordena cada mitad recursivamente, luego fusiona las dos mitades ordenadas en una sola lista ordenada.

Es el primer algoritmo que garantiza O(n log n) en el peor caso sin importar la entrada, y es estable por construcción — los elementos iguales nunca cruzan. A cambio, requiere O(n) espacio auxiliar.

Cómo Funciona

1. Divide: parte el arreglo en dos mitades.
2. Vence: ordena cada mitad recursivamente.
3. Combina: fusiona las dos mitades ordenadas usando un arreglo temporal.

Idea Clave

La garantía O(n log n) viene del árbol de recursión: cada nivel hace O(n) trabajo de merge, y hay log₂ n niveles porque el arreglo se divide por la mitad en cada llamada. No hay peor caso: incluso si el arreglo está inverso, siempre haces la misma cantidad de trabajo.

El paso de merge es lineal: caminas dos punteros por las dos mitades, copiando el menor al arreglo temporal. La estabilidad viene de usar <= (no <) cuando los valores son iguales: el elemento de la izquierda (originalmente anterior) se copia primero.

Ejemplo Trabajado

Ordena [8, 3, 5, 1, 7, 2, 6, 4]:

División (árbol de recursión):

[8,3,5,1,7,2,6,4]
├─ [8,3,5,1]     → [3,5,1,8]
│  ├─ [8,3]      → [3,8]
│  │  ├─ [8]     → base
│  │  └─ [3]     → base
│  └─ [5,1]      → [1,5]
│     ├─ [5]     → base
│     └─ [1]     → base
└─ [7,2,6,4]     → [2,4,6,7]
   ├─ [7,2]      → [2,7]
   │  ├─ [7]     → base
   │  └─ [2]     → base
   └─ [6,4]      → [4,6]
      ├─ [6]     → base
      └─ [4]     → base

Fusión (merge):

• Merge [3,8] + [1,5] = [1,3,5,8]
• Merge [7,2] + [6,4] = [2,4,6,7]
• Merge [1,3,5,8] + [2,4,6,7] = [1,2,3,4,5,6,7,8]

Resultado: [1, 2, 3, 4, 5, 6, 7, 8]. Observa el visualizador mostrar el árbol de recursión y cada merge.

Casos Extremos y Trampas

• “Arreglo ya ordenado — Merge Sort sigue dividiendo y fusionando: O(n log n) work, sin aprovechar el orden existente.”
• Arreglo inverso — mismo O(n log n); no hay peor caso.
• Memoria — requiere O(n) espacio auxiliar. Algunas implementaciones in-place son complejas y pierden estabilidad.
• Cache locality — peor que QuickSort en práctica por los saltos en el arreglo temporal.

Comparación con QuickSort

Aplicaciones

• Ordenamiento externo — datos más grandes que memoria (merge sorted runs)
• Estabilidad requerida — ordenar por múltiples claves (nombre, luego edad)
• Listas enlazadas — merge sin necesidad de arreglo auxiliar
• API estándar — base de Collections.sort() en Java, sorted() en Python (TimSort)

Trayectoria de Práctica

1. Traza Merge Sort en [5, 2, 4, 6, 1, 3], dibujando el árbol de recursión completo.
2. Implementa la función merge(left, right) y prueba con mitades de diferente longitud.
3. Cuenta cuántas comparaciones hace Merge Sort en el peor caso para n=8.
4. Explica por qué Merge Sort es estable, usando el ejemplo [3, 5, 3, 1].
5. Investiga Timsort: ¿por qué Python/Java lo usan en lugar de Merge Sort puro?