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

Пирамидальная сортировка была предложена Дж. Уильямсом в 1964 году.^[1]

Сортировка пирамидой использует бинарное сортирующее дерево. Сортирующее дерево — это такое дерево, у которого выполнены условия:

1. Каждый лист имеет глубину либо ${\displaystyle d}$, либо ${\displaystyle d-1}$, ${\displaystyle d}$ — максимальная глубина дерева.
2. Значение в любой вершине не меньше (другой вариант — не больше) значения её потомков.

Удобная структура данных для сортирующего дерева — такой массив Array, что Array[0] — элемент в корне, а потомки элемента Array[i] являются Array[2i+1] и Array[2i+2].

Алгоритм сортировки будет состоять из двух основных шагов:

1. Выстраиваем элементы массива в виде сортирующего дерева^{[источник не указан 3350 дней]}:

${\displaystyle {\text{Array}}[i]\geq {\text{Array}}[2i+1]}$

${\displaystyle {\text{Array}}[i]\geq {\text{Array}}[2i+2]}$

при ${\displaystyle 0\leq i<n/2}$.

Этот шаг требует ${\displaystyle O(n)}$ операций.

2. Будем удалять элементы из корня по одному за раз и перестраивать дерево. То есть на первом шаге обмениваем Array[0] и Array[n-1], преобразовываем Array[0], Array[1], … , Array[n-2] в сортирующее дерево. Затем переставляем Array[0] и Array[n-2], преобразовываем Array[0], Array[1], … , Array[n-3] в сортирующее дерево. Процесс продолжается до тех пор, пока в сортирующем дереве не останется один элемент. Тогда Array[0], Array[1], … , Array[n-1] — упорядоченная последовательность.

Этот шаг требует ${\displaystyle O(n\log n)}$ операций.

Достоинства

• Имеет доказанную оценку худшего случая ${\displaystyle O(n\cdot \log n)}$.
• Сортирует на месте, то есть требует всего ${\displaystyle O(1)}$ дополнительной памяти (если дерево организовывать так, как показано выше).

Недостатки

• Неустойчив — для обеспечения устойчивости нужно расширять ключ.
• На почти отсортированных массивах работает столь же долго, как и на хаотических данных.
• На одном шаге выборку приходится делать хаотично по всей длине массива — поэтому алгоритм плохо сочетается с кэшированием и подкачкой памяти^[1].
• Методу требуется доступ к произвольному элементу структуры; не работает на связанных списках и других структурах памяти последовательного доступа.
• Не распараллеливается.

Сортировка слиянием при расходе памяти ${\displaystyle O(n)}$ быстрее (${\displaystyle O(n\cdot \log n)}$ с меньшей константой) и не подвержена деградации на неудачных данных.

Из-за сложности алгоритма выигрыш получается только на больших ${\displaystyle n}$. На небольших ${\displaystyle n}$ (до нескольких тысяч) быстрее сортировка Шелла.

Алгоритм «пирамидальная сортировка» активно применяется в ядре Linux.