Time and Space Complexity

Complexité temporelle :

• Cas le meilleur, moyen et le pire : O(n log n)
  • La construction du tas est en O(n), et chacune des n extractions coûte O(log n) pour le tamisage (sift-down). Il n'y a pas de cas d'entrée défavorable qui dégrade cette performance.

Complexité spatiale :

• O(1)
  • Le tri par tas (Heap Sort) réorganise les éléments à l'intérieur du tableau d'origine et ne nécessite qu'une quantité constante de mémoire supplémentaire.

Résumé :

• Le tri par tas combine un temps d'exécution garanti en O(n log n) avec un espace supplémentaire en O(1), une combinaison que le tri fusion (Merge Sort) et le tri rapide (Quick Sort) n'offrent pas tous les deux.
• Il n'est pas stable (les éléments égaux peuvent changer d'ordre relatif), ce qui est son principal compromis.