/* ECP: FILEname=fig9_18.c */
/* 1*/   /* Shellsort An Array Of Unknowns. */
/* 2*/   /* Uses Only 2N Block Copies. */

/* 3*/   void
/* 4*/   Shellsort( void *A, const unsigned int N, const size_t Size,
/* 5*/           int Cmp( const void *, const void * ) ) {

/* 6*/       unsigned int Gap;
/* 7*/       void *Tmp;
/* 8*/       unsigned int i, j;                   /* Loop Counters */
/* 9*/       void **Ptr;          /* Array Of Pointers To Unknowns */
/*10*/       void *ACopy;                          /* Sorted Array */

/*11*/       /* Allocate And Initialize Pointers for Indirect Sort */
/*12*/       if( ( Ptr = malloc( N * sizeof( void * ) ) ) == NULL )
/*13*/           Error( "Out of memory" );
/*14*/       if( ( ACopy = malloc( N * Size ) ) == NULL )
/*15*/           Error( "Out of memory" );
/*16*/       for( i = 0; i < N; i++ )
/*17*/           Ptr[ i ] = A + i * Size;

/*18*/           /* Indirect Shellsort */
/*19*/       for( Gap = N/2; Gap > 0; Gap = Gap == 2 ? 1 : Gap / 2.2 )
/*20*/           for( i = Gap; i < N; i++ )
/*21*/           {
/*22*/               Tmp = Ptr[ i ];
/*23*/               for( j = i; j >= Gap &&
/*24*/                      Cmp( Tmp, Ptr[ j - Gap ] ) < 0; j -= Gap )
/*25*/                   Ptr[ j ] = Ptr[ j - Gap ];
/*26*/               Ptr[ j ] = Tmp;
/*27*/           }

/*28*/       for( i = 0; i < N; i++ )       /* Make Sorted Array */
/*29*/           memcpy( ACopy + i * Size, Ptr[ i ], Size );

/*30*/          /* Copy It Back */
/*31*/       memcpy( A, ACopy,  N * Size );

/*32*/       free( ACopy ); free( Ptr );    /* Clean Up */
/*33*/   }