Time and Space Complexity

Complejidad Temporal:

• Casos Mejor, Promedio y Peor: O(n log n)
  • Construir el montículo (heap) es O(n), y cada una de las n extracciones cuesta O(log n) para el sift-down. No existe ningún caso de entrada desfavorable que lo degrade.

Complejidad Espacial:

• O(1)
  • Heap Sort reorganiza los elementos dentro del arreglo original y solo necesita una cantidad constante de memoria adicional.

Resumen:

• Heap Sort combina un tiempo de ejecución garantizado de O(n log n) con un espacio adicional de O(1), una combinación que Merge Sort y Quick Sort no ofrecen simultáneamente.
• No es estable (los elementos iguales pueden cambiar su orden relativo), lo cual es su principal desventaja.