¿Cuál es la complejidad temporal indicada de merge sort en el peor caso?

O(n log n)

La complejidad temporal de merge sort en el peor caso es O(n log n). El algoritmo de ordenamiento por mezcla (merge sort en inglés) es un algoritmo de ordenamiento externo estable basado en la técnica divide y vencerás. La notación O grande describe cómo crece el trabajo necesario cuando aumenta el tamaño de la entrada.

O(n log n) no representa un número fijo de segundos: expresa una tendencia de crecimiento y permite comparar algoritmos sin depender de un ordenador concreto. Factores constantes y detalles de implementación pueden afectar al tiempo real, pero la clase O(n log n) resume el comportamiento dominante para entradas grandes. Para situar «O(n log n)», el marco de la tecnología permite diferenciar ese dato de conceptos próximos.