/* Рассчитывает последовательность
   приращений по методу Р. Седжвика*/
int Dsedj(int d[], long n) {
    int p1, p2, p3, i;
 
    p1 = p2 = p3 = 1;
    i = -1;
    do {
        if (++i % 2) {
            d[i] = 8*p1 - 6*p2 + 1;
        } else {
            d[i] = 9*p1 - 9*p3 + 1;
            p2 *= 2;
            p3 *= 2;
        }
        p1 *= 2;
    } while(3*d[i] < n);  
 
    return (i > 0) ? --i : 0;
}
 
/* Сортировка Шелла */
template<class T>
void ShellSortDSedj1(T* x) {
    /* максимальное количество рассчитываемых
       приращений = 20 */
    int d, i, j, dseq[20];
    int di;
 
    /* Рассчитываем последовательность
       приращений */
    di = Dsedj(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
       т.е. ко всей последовательности во вложенном цикле
       уже был применен метод пузырька */
}