/*
 * insertion sort
 * 
 * insertion sort using template classes
 *
 * Author: Mark Ruff
 */

template <class T>
void insertion_sort( T* array, int size ) {

  // start at the SECOND element, if we're past the end of the array finish
  for ( int i = 1 ; i < size ; i++ ) {
    T current_value = array[i];
    // compare to all elements prior to the currently selected, starting at the
    // largest (furthest along the array). These will be sorted
    for ( int j = i ; j >= 0  ; j-- ) {
       // if we make it to the start, current must be the smallest element
       if ( j == 0 ) {
         array[j] = current_value;
       }
       // if the current element is smaller than the sorted element, shift
       // the sorted element to the right 
       else if ( current_value < array[j - 1] ) {
         array[j] = array [j - 1];
       // otherwise the current element must be bigger, so slot it in here
       // (any bigger elements have been  moved to the right already)
       }
       else {
         array[j] = current_value;
         break;
       }
    }
  }
}