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

/* 3*/   void
/* 4*/   Shellsort( Block A[ ], const unsigned int N )
/* 5*/   {
/* 6*/       unsigned int Gap;
/* 7*/       Block *Tmp;
/* 8*/       unsigned int i, j;                    /* Loop Counters */
/* 9*/       Block **Ptr;             /* Array Of Pointers To Block */
/*10*/       Block *ACopy;                          /* Sorted Array */

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

/*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*/                      Tmp->Key < Ptr[ j - Gap ]->Key; j -= Gap )
/*25*/                   Ptr[ j ] = Ptr[ j - Gap ];
/*26*/               Ptr[ j ] = Tmp;
/*27*/           }

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

/*30*/       for( i = 0; i < N; i++ )       /* Copy It Back */
/*31*/           A[ i ] = ACopy[ i ];

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