template <class Etype>
inline void
Swap( Etype & A, Etype & B )
{
Etype Tmp = A;
A = B;
B = Tmp;
}
template <class Etype>
void
InsertionSort( Etype A[ ], int N )
{
for( int P = 1; P < N; P++ )
{
Etype Tmp = A[ P ];
int j;
for( j = P; j > 0 && Tmp < A[ j-1 ]; j-- )
A[ j ] = A[ j-1 ];
A[ j ] = Tmp;
}
}
static const int Cutoff = 10;
template <class Etype>
void
QuickSort( Etype A[ ], int Low, int High )
{
if( Low + Cutoff > High )
InsertionSort( &A[ Low ], High - Low + 1 );
else
{
int Middle = ( Low + High ) / 2;
if( A[ Middle ] < A[ Low ] )
Swap( A[ Low ], A[ Middle ] );
if( A[ High ] < A[ Low ] )
Swap( A[ Low ], A[ High ] );
if( A[ High ] < A[ Middle ] )
Swap( A[ Middle ], A[ High ] );
Etype Pivot = A[ Middle ];
Swap( A[ Middle ], A[ High - 1 ] );
int i, j;
for( i = Low, j = High - 1; ; )
{
while( A[ ++i ] < Pivot ) ; while( Pivot < A[ --j ] ) ; if( i < j )
Swap( A[ i ], A[ j ] );
else
break;
}
Swap( A[ i ], A[ High - 1 ] );
QuickSort( A, Low, i - 1 ); QuickSort( A, i + 1, High ); }
}
template <class Etype>
void
QuickSort( Etype A[ ], int N )
{
QuickSort( A, 0, N - 1 );
}