Time and Space Complexity

Complejidad Temporal:

• Casos Mejor, Promedio y Peor: O(n log n)
  • El arreglo se divide a la mitad aproximadamente log n veces, y cada nivel realiza un trabajo de O(n) para fusionar. El tiempo de ejecución no depende del orden de la entrada.

Complejidad Espacial:

• O(n)
  • A diferencia de los ordenamientos in-place, Merge Sort construye nuevos arreglos mientras fusiona, por lo que necesita memoria adicional proporcional al tamaño de la entrada.

Resumen:

• Merge Sort es rápido y predecible: O(n log n) en todos los casos.
• Es estable, por lo que los elementos iguales mantienen su orden.
• La desventaja es la memoria extra O(n) que utiliza para la fusión.