#include <stdlib.h> 
#include <stdio.h>
 
 
#define uint32 unsigned int
 
typedef int (*CMPFUN)(int, int);


/* Calculated from the combinations of  9 * (4^n - 2^n) + 1,
 * and  4^n - 3 * 2^n + 1
 */
uint32 hop_array[] =
{
1,
5,
19,
41,
109,
209,
505,
929,
2161,
3905,
8929,
16001,
36289,
64769,
146305,
260609,
587521,
1045505,
2354689,
4188161,
9427969,
16764929,
37730305,
67084289,
150958081,
268386305,
603906049,
1073643521,
2415771649,
0xffffffff }; 
 
 
void ArraySort(int This[], CMPFUN fun_ptr, uint32 the_len)
{
  /* shell sort */

  int level;

  for (level = 0; the_len > hop_array[level]; ++level);

  do
  {
    uint32 dist;
    uint32 indx;
    
    dist = hop_array[--level];
    for (indx = dist; indx < the_len; ++indx)
    {
      int cur_val;
      uint32 indx2;

      cur_val = This[indx];
      indx2 = indx;
      do
      {
        int early_val;
        early_val = This[indx2 - dist];
        if ((*fun_ptr)(early_val, cur_val) <= 0)
          break;
        This[indx2] = early_val;
        indx2 -= dist;
      } while (indx2 >= dist);
      This[indx2] = cur_val;
    }
  } while (level >= 1);
}

 
#define ARRAY_SIZE 250000
 
int my_array[ARRAY_SIZE];
 
uint32 fill_array()
{
  int indx;
  uint32 checksum = 0;
  for (indx=0; indx < ARRAY_SIZE; ++indx)
  {
    checksum += my_array[indx] = rand();
  }
  return checksum;
}
 
int cmpfun(int a, int b)
{
  if (a > b)
    return 1;
  else if (a < b)
    return -1;
  else
    return 0;
}
 
int main()
{
  int indx;
  uint32 sum1;
  uint32 sum2;
 
  sum1 = fill_array();
 
  ArraySort(my_array, cmpfun, ARRAY_SIZE);
 
  for (indx=1; indx < ARRAY_SIZE; ++indx)
  {
    if (my_array[indx - 1] > my_array[indx])
    {
      printf("bad sort\n");
      return(1);
    }
  }
  for (indx = 0; indx < ARRAY_SIZE; ++indx)
  {
    sum2 += my_array[indx];
  }
  if (sum1 != sum2)
  {
    printf("bad checksum\n");
    return(1);
  }
  return(0);
}