/* ECP: FILEname=fig9_16.c */
/* 1*/   /* Shellsort An Array Of Blocks. */
/* 2*/   /* Avoid Excessive Copying And Extra Array Of Blocks */

/* 3*/   void
/* 4*/   Shellsort( Block A[ ], const unsigned int N )
/* 5*/   {
/* 6*/       unsigned int Gap;
/* 7*/       Block *Tmp;
/* 8*/       unsigned int i, j, NextJ;            /* Loop Counters */
/* 9*/       Block **Ptr;            /* Array Of Pointers To Block */
/*10*/       int *Rank;    /* Array Listing Correct Final Position */
/*11*/       Block ShuffleTmp; /* Temp for The Final Rearrangement */

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

/*19*/       /* Indirect Shellsort (Omitted -- Figure 9.15, 19-27) */
/*20*/           /* Determine Correct Positions */
/*21*/       for( i = 0; i < N; i++ )
/*22*/           Rank[ i ] = Ptr[ i ] - &A[ 0 ];

/*23*/           /* Shuffle It Back */
/*24*/       for( i = 0; i < N; i++ )
/*25*/           if( Rank[ i ] != i )
/*26*/           {
/*27*/               ShuffleTmp = A[ i ];
/*28*/               for( j = i; Rank[ j ] != i; j = NextJ )
/*29*/               {
/*30*/                   A[ j ] = A[ Rank[ j ] ];
/*31*/                   NextJ = Rank[ j ];
/*32*/                   Rank[ j ] = j;
/*33*/               }
/*34*/               A[ j ] = ShuffleTmp;
/*35*/               Rank[ j ] = j;
/*36*/           }

/*37*/       free( Rank ); free( Ptr ); /* Clean Up */
/*38*/   }