//
//  File:  insert.h
//
//  Code for insertion sort

template <class T>
void
Insertion_Sort( T A[ ], int N )
{
  T tmp;

  for( int i = 1; i < N; i++ ) {
    tmp = A[ i ];
    int j = i-1;
    while ( j >= 0 && tmp < A[ j ] ) {
      A[ j+1 ] = A[ j ];
      -- j;
    }
    A[ j+1 ] = tmp;
  }
}