template 
void
insertion_sort(T a[], int n) {

  // Re-arrange the array elements a[0..n-1] 
  // so they are in ascending order.

  for (int i = 0; i < n - 1; i++) {
    int gap = i + 1;
    const T t = a[gap];
    while ((gap > 0) and (a[gap - 1] > t)) {
      a[gap] = a[gap - 1];
      gap--;
      }
    a[gap] = t;
    }
  }