Void Heapify (int a[], int pos, int n)

{ int t, tm;

while (2*pos + 1 < n)

{ t = 2*pos +1;

if (2*pos+2<n && A[2*pos+2] >= A[t])

t = 2*pos + 2;

if (A[pos] < A[t])

{ tm = A[pos]; A[pos] = A[t];

A[t] = tm; pos = t;

}

else break;

}

}

Void PiramSort(int a[], int n)

{ int tm;

for (int i = n - 1; i >= 0; i--)

Heapify(A, i, n);

while(n>0)

{ tm = A[0]; A[0] = A[n-1];

A[n-1] = tm; n--;

Heapify(A, 0, n);

}

}

Void main()

{ int n; int A[100];

cout<<"Razmer "; cin>>n;

for(int i = 0; i < n; i++)

{ cout<<"Number= "; cin>> A[i]; }

PiramSort(A, n);

for(int i = 0; i < n; i ++)

cout << A[i]<<' ';

}

Преимущество ал­го­рит­ма в том, что пи­ра­ми­да хра­нит­ся пря­мо в ис­ход­ном мас­си­ве. По ме­ре то­го, как раз­мер пи­ра­ми­ды умень­ша­ет­ся, она за­ни­ма­ет всё мень­шую часть мас­си­ва, а ре­зуль­тат сор­ти­ров­ки за­пи­сы­ва­ет­ся, на­чи­ная с кон­ца мас­си­ва на осво­бо­див­шие­ся от пи­ра­ми­ды ме­ста.

Пирамидальная сортировка проигрывает быстрой сортировке по эффективности для больших массивов (в 1,5 раза медленнее).

Среднее число пересылок - (n*logn)/2

Трудоемкость  O(nlog(n)).

Другая программа

#include <iostream>

#include <conio.h>

using namespace std;

Void iswap(int &n1, int &n2)

{ int temp = n1; n1 = n2; n2 = temp;}

Int main()

{ int const n = 100; int a[n];

for ( int i = 0; i < n; ++i ) { a[i] = n - i; cout << a[i] << " "; }

bool b = false; int sh = 0; //смещение

for(;;)

{ b = false; for ( int i = 0; i < n; i++ )

{ if( i * 2 + 2 + sh < n )

{ if((a[i+sh]> a[i*2+1+sh]) || (a[i+sh]>a[i * 2 + 2 + sh]))

{ if ( a[i * 2 + 1 + sh] < a[i * 2 + 2 + sh] )

{ iswap( a[i + sh], a[i * 2 + 1 + sh] ); b = true; }

Else if ( a[i * 2 + 2 + sh] < a[ i * 2 + 1 + sh])

{ iswap( a[ i + sh], a[i * 2 + 2 + sh]); b = true; }

}

//дополнительная проверка для последних двух элементов

//с помощью этой проверки можно отсортировать пирамиду

//состоящую всего лишь из трех элементов

if( a[i*2 + 2 + sh] < a[i*2 + 1 + sh] )

{ iswap( a[i*2+1+sh], a[i * 2 +2+ sh] ); b = true; }

}

else if( i * 2 + 1 + sh < n )

{ if( a[i + sh] > a[ i * 2 + 1 + sh] )

{ iswap( a[i + sh], a[i * 2 + 1 + sh] ); b = true; } }

}

if (!b) sh++; //смещение увелич. когда на тек. этапе сортировать нечего

if ( sh + 2 == n ) break; } //конец сортировки

cout << endl << endl;

for ( int i = 0; i < n; ++i ) cout << a[i] << " ";

return 0; }

Сортировка слиянием

 Сортировка слиянием предполагает последовательный доступ к элементам сортируемых последовательностей. 

Алгоритм является рекурсивным.

Если из упорядоченных последовательностей брать по одному очередному элементу, выбирать из них минимальный и переносить его в результирующую последовательность, то выходная последовательность будет упорядоченной.

Отсюда возможен простой способ однократного слияния: массив разбивается на n частей, каждая из них сортируется независимо, а затем отсортированные части объединяются слиянием.  

Пусть исходный массив делится на две части.

#include <iostream>

using namespace std;