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

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

• Отцом к является узел [k/2]
• Потомками узла к являются 2к и 2к+1

Пирамидой будем называть дерево удовлетворяющие написаным выше правилам и к ним еще плюс:

k[j/2]>=k[j]

1<=[j/2]<j<=N

Procedure shift(L,R: integer);
var
i,j:integer;
x: integer;
Begin
i:=L;
j:=2*L;
x:=A[L];
if (j<R) and (A[j]<A[j+1]) then
j:=j+1;
while (j<=R) and (x<A[j]) do
begin
A[i]:=A[j];
i:=j;
j:=2*j;
if (j<R) and (A[j]<A[j+1]) then
inc(j);
end;
A[i]:=x;
end;

Пример исспользования:

L:=(N div 2)+1;
R:=N;
while L>1 do
begin
L:=L-1;
shift(L,R);
end;
while (R>1) do
begin
x:=A[1];
A[1]:=A[R];
A[R]:=x;
R:=R-1;
shift(L,R);
end;