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

Построение (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, и т.д. В результате получим обратно отсортированный массив.

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

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

К	У	Р	А	П	О	В	А
				П	О	В	А	пирамида
			А	П	О	В	А	пирамида
		Р	А	П	О	В	А
		В	А	П	О	Р	А	пирамида
	У	В	А	П	О	Р	А
	А	В	У	П	О	Р	А
	А	В	А	П	О	Р	У	пирамида
К	А	В	А	П	О	Р	У
А	К	В	А	П	О	Р	У
А	А	В	К	П	О	Р	У	пирамида

Сортировка

А	А	В	К	П	О	Р	У
У	А	В	К	П	О	Р	А
А	У	В	К	П	О	Р
А	К	В	У	П	О	Р		пирамида
Р	В	К	У	П	О	А
В	Р	К	У	П	О
В	П	К	У	Р	О			пирамида
О	П	К	У	Р	В
К	П	О	У	Р				пирамида
Р	П	О	У	К
О	П	Р	У					пирамида
У	П	Р	О
П	У	Р						пирамида
Р	У	П						пирамида
У	Р							пирамида
У	Р	П	О	К	В	А	А

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