Метод пирамидальной сортировки был разработан английским математиком Дж. Уильямсом. В основе метода - удобная нумерация вершин двоичного дерева и связь дерева с массивом.
Рассмотрим полное двоичное дерево с ветвями высоты k. Такое дерево имеет 2^(k+1) - 1 вершин(таким образом, зависимость высоты дерева от числа вершин почти логарифмическая). Действительно, корневая вершина образует нулевой слой этого дерева, далее в каждом горизонтальном слое число вершин вдвое больше, чем в предыдущем, а слой k содержит 2^k вершин. Если перенумеровать вершины сверху вниз и слева направо, то легко убедиться, что вершина с номером s соединится с вершинами 2s и 2s + 1 следующего слоя (дети этой вершины).
Иерархическая сортировка основана на этом способе нумерации. Каждому индексу массива ставится в соответствие единственная вершина, а элементы массива (обозначим его через h[1:n]) могут рассматриваться как вершины двоичного дерева. В терминах этого дерева и происходит сортировка массива. Простая арифметическая связь номеров соединённых вершин позволяет перевести эти элементы в индексы.
Сортировка состоит из двух фаз. Первая фаза обеспечивает иерархическую упорядоченность массива: значение в каждой вершине должно быть хуже (так как сортировка традиционно осуществляется по возрастанию, то под словом "хуже" понимается "больше"), чем у детей. Для этого используется операция просеивания элемента: текущий элемент сравнивается с худшим из элементов-детей, и если ребёнок хуже, то они меняются местами. На новом месте операция для текущего элемента повторяется. Так просеивается каждый элемент начиная с номера [n/2] (почему не с номера n) и кончая первым.
Вторая фаза сортировки состоит из последовательного выполнения следующих действий: взять самый худший элемент (он сейчас на первом месте, а должен быть на последнем), поменять его местами с последним, сократить на единицу число вершин в дереве, отцепив последний элемент, "утопить" верхний элемент дерева, чтобы восстановить иерархическую упорядоченность. В конце концов, когда все элементы массива окажутся отцеплены от дерева, массив будет полностью упорядочен.