Mergesort

Descrito por John von Neumann en 1945, lo que lo convierte en uno de los algoritmos más antiguos que siguen en producción. El paso de fusión recorre dos listas ya ordenadas y toma cada vez el menor de los dos elementos frontales, lo que es lineal; la recursión tiene profundidad log n; el producto es la complejidad garantizada.

Dos propiedades lo hacen difícil de reemplazar. Es estable — los elementos iguales conservan su orden relativo, algo necesario al ordenar por varios campos en secuencia. Y solo lee de forma secuencial, lo que lo convierte en la opción estándar para datos demasiado grandes para la memoria: las ordenaciones externas en disco y cinta siguen apoyándose en el mergesort. El coste es O(n) de memoria extra, donde Quicksort casi no necesita ninguna pero degenera a tiempo cuadrático en el peor caso. Las ordenaciones por defecto de Python y Java usan Timsort, un híbrido que por debajo es mergesort.