Time and Space Complexity

Complexidade de Tempo:

• Melhor, Médio e Pior Caso: O(n log n)
  • A construção do heap é O(n), e cada uma das n extrações custa O(log n) para o sift-down. Não há caso de entrada ruim que o degrade.

Complexidade de Espaço:

• O(1)
  • O Heap Sort rearranja os elementos dentro do array original e precisa apenas de uma quantidade constante de memória extra.

Resumo:

• O Heap Sort combina um tempo de execução garantido de O(n log n) com espaço extra O(1), uma combinação que o Merge Sort e o Quick Sort não oferecem simultaneamente.
• Ele não é estável (elementos iguais podem mudar de ordem relativa), o que é sua principal desvantagem.