ヒープソート(昇順)

ポイントは親と２つの子の３要素について最小値が親にあるようにすることです。下から順に上げていけば、前記条件に合致するヒープが完成し、そのヒープのルートが、ソート対象となるノード集合の最小値になります。
下のコードでは、ソート対象の先頭を指すポインタをひとつずつ後ろに進めることで、常にheadから始まるノード集合がソート対象となるようになっています。

下の枠内の28行目に誤りがありました。
if( a[n2] >= a[n2+1] ) {は誤りで、if( a[n2] < a[n2+1] ) {が正しいです(下では訂正済み)。

(配列のサイズ=size で、添字は 0 から size-1)
(SWAPマクロは自前で用意)

sort( int a[], int size ) {
  int* head;
  int range;

  for( range = size, head = a; range > 0; range--, head++ ) {
    // 現在の head が非ソート済領域の先頭
    int n = size/2 - 1
    int n2 = size - 1

    if( n % 2 == 0 ) {
      // 最初のチェック対象の子がひとつだけの場合
      if( head[n] > head[n2] ) {
        SWAP(head[n],head[n2]);
      }
      n--;
      n2 -= 2;
    }
    else {
      // 最初のチェック対象の子が二つある場合→while内で処理を行う
      n2--;
    }

    while( n >= 0 ) {
      // 親と子をヒープにあうように入れ替える
      if( a[n2] < a[n2+1] ) {
        // n と n2
        if( a[n] > a[n2] ) {
          SWAP(a[n],a[n2]);
        }
      }
      else {
        // n と n2+1
        if( a[n] > a[n2+1] ) {
          SWAP(a[n],a[n2+1]);
        }
      }

      // 次へ
      n--;
      n2 -= 2;
    }  // while ループ終端

  }  // for ループ終端

}