Пирамидальная сортировка (Heapsort)

Коротко: Heapsort сортирует, превращая данные в max-кучу и затем многократно перемещая наибольший элемент в конец.

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

Подробности

• Шаг 1: Массив за O(n) превращается в max-кучу: от середины назад каждый узел «просеивается» вниз.
• Шаг 2: Корень (наибольший элемент) меняется местами с последним элементом. Куча уменьшается на 1, новый корень просеивается.
• Повторять, пока куча не опустеет. Массив тогда отсортирован по возрастанию.
• Свойства: не устойчива, на месте (in place), не зависит от предварительной упорядоченности.
• Применение: Как запасной вариант в introsort, если быстрая сортировка уходит в слишком глубокую рекурсию. Сравните куча и очередь с приоритетом.

См. также: Сортировка слиянием