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

static void index_downheap(unsigned int *, const double *, const unsigned int, unsigned int);
void double_sort_index(unsigned int *, const double *, const unsigned int);

void double_sort_index(unsigned int *p, const double *list, const unsigned int n)
{
  unsigned int N;
  unsigned int i, k;

  if ( n == 0 )
    return;

  for ( i = 0 ; i < n ; i++ )
    p[i] = i;

  N = n - 1;

  k = N / 2;
  k++;
  do
  {
      k--;
      index_downheap( p, list, N, k );
  }
  while ( k > 0 );

  while ( N > 0 )
  {
    unsigned int tmp = p[0];
    p[0] = p[N];
    p[N] = tmp;

    index_downheap( p, list, --N, 0 );
  }
}

static void index_downheap(unsigned int *p, const double *list, const unsigned int N, unsigned int k)
{
  const unsigned int pki = p[k];
  
  while ( k <= N / 2 )
  {
      unsigned int j = 2 * k;

      if ( (j < N) && (list[p[j]] < list[p[j]+1]) )
      {
        j++;
      }
    
      if ( !(list[pki] < list[p[j]]) )
      {
        break;
      }
  
      p[k] = p[j];

      k = j;
  }

  p[k] = pki;
}

int main(int argc, char *argv[])
{
  int i;
  unsigned int *perm;
  double *x;

  x = (double *) malloc( 5 * sizeof(double) );

  x[0]=10.0;
  x[1]=9.0;
  x[2]=8.0;
  x[3]=7.0;
  x[4]=6.0;

  for( i=0; i < 5; i++ )
    printf("%f\n", x[i]);

  perm = (unsigned int *) malloc ( 5 * sizeof(unsigned int) );

  double_sort_index(perm, x, 5);

  printf("\n--SORTED?--\n");

  for( i=0; i < 5; i++ )
    printf("%f\n", x[perm[i]]);

  exit(0);
}