Алгоритм на псевдокоде

Построение (L,R)-пирамиды

a_L+1,…,a _R – на входе пирамида (L+1,R)

a_L –новый элемент

x:= a_L, i:=L

DO

j:=2i

IF (j>R) OD

IF((j<R) и (a_j+1£ a_j)) j=j+1 FI

IF (x£a_j) OD

a_i= a_j

i:=j

OD

a_i:=x

Величины М и С в процессе построения (L, R)-пирамиды имеют следующие оценки M_пир≤log (R/L)+2, C_пир≤2 log (R/L)

Пирамидальная сортировка производится в два этапа. Сначала строится пирамида из элементов массива. По свойству (3) правая часть массива является (n/2+1, n)-пирамидой. Будем добавлять по одному элементу слева, расширяя пирамиду, пока в неё не войдут все элементы массива. Тогда по свойству (2) первый элемент последовательности – минимальный.

Произведём двустороннее усечение: уберём элементы a₁,a_n. По свойству (1) оставшаяся последовательность является (2, n-1)-пирамидой. Элемент a₁ поставим на последнее место, а элемент a_n добавим к пирамиде a₂,…,a_n-1 слева. Получим новую (1, n-1)-пирамиду. В ней первый элемент является минимальным. Поставим первый элемент пирамиды на позицию n-1, а элемент a_n-1 добавим к пирамиде a₂,…,a_n-1, и т.д. В результате получим обратно отсортированный массив.

Пример. Отсортировать слово методом пирамидальной сортировки.