Kompleksitas Waktu dan Ruang

Kompleksitas Waktu:

• Kasus Terbaik, Rata-rata, dan Terburuk: O(n log n)
  • Membangun heap membutuhkan O(n), dan setiap ekstraksi dari n elemen membutuhkan O(log n) untuk sift-down. Tidak ada kasus input buruk yang membuat kompleksitasnya menurun.

Kompleksitas Ruang:

• O(1)
  • Heap Sort menyusun ulang elemen di dalam array asli dan hanya membutuhkan memori tambahan dalam jumlah konstan.

Ringkasan:

• Heap Sort menggabungkan waktu eksekusi O(n log n) yang terjamin dengan ruang tambahan O(1), kombinasi yang tidak ditawarkan oleh Merge Sort maupun Quick Sort.
• Algoritma ini tidak stabil (elemen yang sama dapat berubah urutan relatifnya), yang merupakan kompromi utamanya.