/* Рассчитывает последовательность
   приращений рекомендуюмую при больших
   размерах сортируемой последовательности */
int DForBigN(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 ShellSortDForBigN(T* x) {
    /* максимальное количество рассчитываемых
       приращений = 20 */
    int d, i, j, dseq[20];
    int di;
 
    /* Рассчитываем последовательность
       приращений */
    di = DForBigN(dseq, n);
 
    while (di >= 0) {
        /* Приращение на данном шаге */
        d = dseq[di--];
 
        /* этот цикл делает проход "пузырька" в том числе и
           для последней последовательности, когда d=1, поэтому
           вызывать в конце InsertSort или какую-либо другую
           элементарную сортировку - не требуется */
        for (i = d; i < n; i++) {
            T tmp = x[i];
            for (j = i-d; (j >= 0) && (x[j] > tmp); j -= d) {
                x[j+d] = x[j];
            }
            x[j+d] = tmp;
        }
    }
    /* Не требуется вызывать InsertSort или BubbleSort
       т.е. ко всей последовательности во вложенном цикле
       уже был применен метод пузырька */
}