Merge Sort

Merge Sort es otro algoritmo de ordenación basado en la estrategia divide y vencerás. Merge Sort siempre divide primero y combina después, a diferencia de Quick Sort que elige un pivote y organiza alrededor de él.

La idea básica es:

1. Dividir la lista en mitades hasta que cada sublista tenga un solo elemento (o esté vacía).
2. Combinar (merge) esas sublistas de manera que queden ordenadas.
3. Repetir el proceso hasta reconstruir la lista completa, ya ordenada.

Paso a paso con un ejemplo

Supongamos que queremos ordenar esta lista:

[8, 3, 1, 7, 0, 10, 2]

Paso 1: Dividir la lista

Dividimos la lista en dos mitades:

Izquierda: [8, 3, 1]
Derecha: [7, 0, 10, 2]

Paso 2: Dividir de nuevo hasta sublistas de un elemento

• Izquierda [8, 3, 1] → [8] y [3, 1] → [3] y [1]
• Derecha [7, 0, 10, 2] → [7, 0] y [10, 2] → [7] y [0], [10] y [2]

Ahora cada sublista tiene un solo elemento, que por definición ya está ordenada.

Paso 3: Combinar sublistas ordenadas

Combinar [3] y [1]:

[1, 3]

Combinar [8] y [1, 3]:

[1, 3, 8]

Combinar sublistas de la derecha:

• [7] y [0] → [0, 7]
• [10] y [2] → [2, 10]
• Combinar [0, 7] y [2, 10] → [0, 2, 7, 10]

Paso 4: Combinar las mitades finales

Combinar [1, 3, 8] y [0, 2, 7, 10]:

[0, 1, 2, 3, 7, 8, 10]

Ahora la lista completa está ordenada.

Resumen visual del proceso

[8, 3, 1, 7, 0, 10, 2]
→ [8, 3, 1] y [7, 0, 10, 2]
→ [8], [3,1] y [7,0], [10,2]
→ [8], [3],[1] y [7],[0],[10],[2]
→ Combinar: [1,3], [8] → [1,3,8]
→ Combinar: [0,7], [2,10] → [0,2,7,10]
→ Combinar finales → [0,1,2,3,7,8,10]