Time and Space Complexity

Zaman Karmaşıklığı:

• En İyi, Ortalama ve En Kötü Durum: O(n log n)
  • Yığını (heap) oluşturmak O(n)'dir ve n adet çıkarmanın her biri aşağı kaydırma (sift-down) işlemi için O(log n) maliyetindedir. Performansını düşüren herhangi bir kötü girdi durumu yoktur.

Alan Karmaşıklığı:

• O(1)
  • Yığın Sıralaması (Heap Sort), öğeleri orijinal dizi içinde yeniden düzenler ve yalnızca sabit miktarda ek belleğe ihtiyaç duyar.

Özet:

• Yığın Sıralaması, garantili O(n log n) çalışma süresini O(1) ek alanla birleştirir; bu, Birleştirmeli Sıralama (Merge Sort) ve Hızlı Sıralamanın (Quick Sort) her ikisinin birden sunmadığı bir kombinasyondur.
• Kararlı (stable) değildir (eşit öğelerin göreceli sırası değişebilir), bu da onun ana ödünleşimidir.