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

Каждый узел имеет 2 (или более) потомка. Значение в потомках меньше, чем в вершине. Таким образом, на вершине дерева мы имеем наибольший узел. Все дерево или пирамида располагаются в одномерном массиве. Координаты легко вычисляются.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define LEFT(i)  ((i<<1)+1)  //i*2 + 1
#define RIGHT(i) ((i<<1)+2)
#define SWAP(v,a,b)  {int tmp=v[a];v[a]=v[b];v[b]=tmp;}

void heapify(int v[], int i, int N){
 while(1){
  int left=LEFT(i), right=RIGHT(i), largest=i;
  if(left<N && v[left]>v[i]) largest=left;
  if(right<N && v[right]>v[largest])largest=right;
  if(largest!=i){
    SWAP(v,i,largest);
    i = largest;
  }else 
    return;
 }
}
int pop(int v[],int N){
  if(N<=0)
    return -1;
  int top = v[0];
  v[0] = v[N-1];
  heapify(v,0,N-1);
  return top;
}
void heapSort(int v[],int N){
  int i = (N-2)/2;
  while(i>=0){
    heapify(v,i--,N);
  }
}

void heapSort1(int v[],int N){
  int i,index,parent;
  for(i = 0; i < N;i++){
    index=i;
    while(index!=0){
      parent = (index-1)/2;
      if(v[index]<=v[parent]) 
        break;
      SWAP(v,index,parent);
      index=parent;
    }
  }
}

#define N 10
int main(){
 int v[N];
 int j;

 srand(time(0));
 for(j=0;j<N;j++)
  v[j] = rand()%20;

 heapSort1(v,N);
 for(j = N; j > 0; j--)
   printf("%d, ", pop(v,j));
 printf("\n");

 return 0;
}