Time and Space Complexity

Временная сложность:

• Лучший, средний и худший случаи: O(n log n)
  • Построение кучи занимает O(n), а каждое из n извлечений стоит O(log n) для просеивания вниз (sift-down). Не существует случая с плохими входными данными, который бы ухудшил производительность.

Пространственная сложность:

• O(1)
  • Пирамидальная сортировка (Heap Sort) переставляет элементы внутри исходного массива и требует лишь константный объем дополнительной памяти.

Резюме:

• Пирамидальная сортировка сочетает в себе гарантированное время выполнения O(n log n) с O(1) дополнительного пространства — комбинация, которую не предлагают одновременно сортировка слиянием (Merge Sort) и быстрая сортировка (Quick Sort).
• Она не является стабильной (равные элементы могут изменить относительный порядок), что является ее основным недостатком.