template<class T>
void swap(T* x, int i, int j) {
    T tmp;
    tmp = x[i]; x[i] = x[j]; x[j] = tmp;
}
 
/* Рассчитывает последовательность
   приращений рекомендуюмую при больших
   размерах сортируемой последовательности */
int DForBig2(int d[], long n) {
    int i = 0;
    d[i] = 1;
 
    do {
        i++;
        d[i] = 3*d[i-1] + 1;
    } while (d[i] < n);
 
    return (i < 2) ? 0 : i-2;
}
 
/* Сортировка Шелла */
template<class T>
void BaseShellSortDForBigN(T* x) {
    /* максимальное количество рассчитываемых
       приращений = 20 */
    int d, i, j, dseq[20];
    int di;
 
    /* Рассчитываем последовательность
       приращений */
    di = DForBigN(dseq, n);
    while (di > 0) {
        /* Приращение на данной итерации */
        d = dseq[di--];
        int i = 0, j = 0;
 
        /* Делает проход пузырька для групп
           пока расстояние между сортируемыми
           элементами не станет = 1 */
        while (j = i + d < n) {
            if (x[i] > x[j]) {
                swap(x, i, j);
            }
            i++;
        }
    }
    /* Заключительная элементарная сортировка
       полученной последовательности из 2-х 
       отсортированных групп */
    InsertSort(x);
}