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
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
| Mejor | O(n log n) |
|---|---|
| Media | O(n log n) |
| Peor | O(n log n) |
| Espacio | O(n) |
| Estable | Sí |
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