Анализ HeapSort
На первый взгляд вовсе не очевидно, что такой метод сортировки даёт хорошие результаты. Ведь в конце концов большие элементы, прежде чем попадут на своё место в правой части, сначала сдвигаются влево. И действительно, процедуру не рекомендуется применять для небольшого количества элементов.
В худшем случае нужно n/2 сдвигающих шагов, они сдвигают элементы на log2(n/2), log2(n/2-1), ..., log2(n-1) позиций (двоичные(!) логарифмы округляются везде до следующего меньшего целого). Следовательно, фаза сортировки требует n-1 сдвигов с самое большое log2(n-1), log2(n-2), ..., 1 перемещениями. Кроме того, нужно ещё n-1 перемещений для просачивания сдвинутого элемента на некоторое расстояние вправо. Эти соображения показывают, что даже в самом плохом из возможных случаев пирамидальная сортировка потребует n * log2 n шагов. Великолепная производительность в таких плохих случаях – одно из привлекательных свойств HeapSort.
Совсем не ясно, когда ожидать наихудшей (или наилучшей) производительности. Но вообще-то кажется, что HeapSort хорошо работает на последовательностях, в которых элементы более или менее отсортированы в обратном порядке. Поэтому её поведение несколько неестественно. Если мы имеем дело с обратным порядком, то фаза порождения пирамиды не требует каких-либо перемещений. Среднее число перемещений приблизительно равно n/2 * log2 n, причём отклонения от этого значения относительно невелики.
