Фундаментальность задачи. 
Классика алгоритмизации

Многие ученые в области вычислительной техники рассматривают эту задачу как наиболее фундаментальную при изучении алгоритмов. Тому есть несколько причин:

• 1. Часто в алгоритмах сортировка используется в качестве ключевой подпрограммы.
• 2. Имеется большой выбор алгоритмов сортировки, в которых применяются самые разные технологии. Фактически в алгоритмах сортировки используются многие важные методы, применяемые при разработке различных классов алгоритмов. В этом отношении задача сортировки представляет также исторический интерес.
• 3. В процессе реализации алгоритмов сортировки на передний план выходят многие прикладные проблемы. Выбор наиболее производительной программы сортировки зависит от многих факторов, многие из которых лучше решать на уровне алгоритма, а не настройкой кода.

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

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

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

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

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

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

Рассчитаем быстродействие построения сортирующего дерева в самом плохом случае. Пусть массив уже отсортирован по возрастанию, и каждый добавляемый элемент вынужден просеиваться вверх до самого корня. Тогда при добавлении элемента номер i нам потребуется операций. Мы делаем эту процедуру для всех i от 0 до :

(1).

Оценим сумму в выражении (1) с помощью определённого интеграла:

(2).

Вычисляя интегралы, получаем:

(3).

Это означает, что затраченное время T (n) равно.

(4).

Так как процедура сортировки дерева полностью аналогична построению дерева методом просеивания вверх, только производится «в обратном порядке»: пирамида не строится, а «разбирается» элемент-за-элементом, и элементы просеиваются не вверх, а вниз, то время работы алгоритма пирамидальной сортировки будет определяться аналогично формуле (4):

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

Достоинства:

Имеет доказанную оценку худшего случая.

Не требует дополнительной памяти.

Недостатки:

Сложен в реализации.

На почти отсортированных массивах работает столь же долго, как и на хаотических данных.