template
void insertSort(T a[], long size) {
  T x;
  long i, j;
 
  for ( i=0; i < size; i++) {  // цикл проходов, i - номер прохода
    x = a[i];   
        // поиск места элемента в готовой последовательности 
    for ( j=i-1; j>=0 && a[j] > x; j--)
      a[j+1] = a[j];    // сдвигаем элемент направо, пока не дошли
        // место найдено, вставить элемент
    a[j+1] = x;
  }
}

// сортировка вставками со сторожевым элементом
template
inline void insertSortGuarded(T a[], long size) {
T x;
long i, j;
T backup = a[0]; // сохранить старый первый элемент
 
setMin(a[0]); // заменить на минимальный
 
// отсортировать массив
for ( i=1; i < size; i++) {
x = a[i];
 
for ( j=i-1; a[j] > x; j--)
a[j+1] = a[j];
a[j+1] = x;
}
 
// вставить backup на правильное место
for ( j=1; j< backup; j++)
a[j-1] = a[j];
 
// вставка элемента
a[j-1] = backup;
}