Ordenamiento por mezcla
Divide la lista por la mitad, ordena cada mitad y luego fusiona las dos mitades ordenadas en una sola lista ordenada.
- Ω(n log n)
- Θ(n log n)
- O(n log n)
- O(n)
- sí
- no
Mejor caso: cómo crece el tiempo con el tamaño n de la lista cuando la entrada es la más fácil para este algoritmo.
Caso medio: cómo suele crecer el tiempo con n. Con n², el doble de valores tarda unas cuatro veces más; n log n crece mucho más despacio.
Peor caso: el crecimiento con la entrada más difícil. Útil cuando la velocidad nunca debe caer.
Espacio: cuánta memoria extra hace falta además de la lista. 1 son unas pocas variables; n, una copia de la lista.
Estable: dos valores iguales conservan su orden original. Importa al ordenar registros por un solo campo.
Sin memoria extra: ordena dentro de la propia lista, sin una segunda lista.
- comparando
- moviendo
- en su lugar final
Prueba esto: Elige pocos valores únicos. Si dos valores son iguales, se toma primero el de la mitad izquierda, así que los iguales conservan su orden.
Cómo funciona
Divide la lista una y otra vez hasta que cada trozo tiene un solo valor, que ya está ordenado. Luego fusiona los trozos de dos en dos: compara los primeros valores de ambos trozos y toma el menor, una y otra vez. La fila elevada de la animación es el espacio extra que se usa al fusionar.
Cuándo es una buena opción
Cuando necesitas una velocidad que siga siendo buena incluso en el peor caso y los valores iguales deben conservar su orden. Python y Java usan una versión del ordenamiento por mezcla. Su desventaja es la memoria extra que necesita.