shell_sort.hpp

#pragma once

template<class T>
inline void insert_sort(vector<T> &vec, size_t g) {
    for (size_t i = g; i < vec.size(); ++i) {
        int v = vec[i];
        int j = i - g;
        while (0 <= j && v < vec[j]) {
            vec[j + g] = vec[j];
            j -= g;
        }
        A[j + g] = v;
    }
}


template<class T>
inline void shell_sort(vector<T> &vec) {
    vector<size_t> H = {1};
    if (3 <= vec.size()) {
        H.push_back(3);
    }
    size_t k = 2;
    size_t next = (1 << (2 * k)) + 3 * (1 << (k - 1)) + 1;
    while (next < vec.size()) {
        H.push_back(next);
        ++k;
        next = (1 << (2 * k)) + 3 * (1 << (k - 1)) + 1;
    }
    for (auto it = H.rbegin(); it != H.rend(); ++it) {
        insert_sort(vec, *it);
    }
}