Ordenamiento por fusión (Merge Sort)

Mira cómo merge sort divide el arreglo a la mitad y lo vuelve a fusionar ordenado. O(n log n) garantizado, a costa de O(n) extra.

Algoritmo

Arreglo

Tamaño48
ComparandoIntercambioPivote/claveLecturaOrdenado
Velocidad50×

Comparaciones

0

Intercambios

0

Paso

0/535

Lecturas

0

Memoria aux.

0

Profundidad

1/1

Baja la velocidad y usa «Paso» para contrastar el resaltado del pseudocódigo con los colores de las barras.

Pseudocódigo

mergeSort(lo, hi)

mid ← (lo+hi)/2

mergeSort(lo,mid) mergeSort(mid+1,hi)

while left & right remain

a[k] ← smaller of the two fronts

copy merged run back

Complejidad

MejorO(n log n)
MediaO(n log n)
PeorO(n log n)
EspacioO(n)
EstableSí

Merge sort es el clásico divide y vencerás: parte el arreglo a la mitad hasta llegar a elementos sueltos y luego fusiona comparando los frentes de cada tramo ordenado.

La profundidad de división es log n y cada nivel toca los n elementos: O(n log n) en el mejor, medio y peor caso. Es estable pero requiere O(n) de espacio temporal. Visualizador de ordenamiento

Preguntas frecuentes

¿Merge sort o quicksort?
Merge garantiza O(n log n) y es estable; quicksort suele ser más rápido en la práctica pero puede degradar a O(n²).
¿Por qué necesita memoria extra?
Fusionar en el mismo arreglo sobrescribiría valores aún no leídos: hace falta un buffer O(n).

Otros algoritmos