Shell Sort

Для заданного gap массив мысленно разбивается на gap независимых подпоследовательностей — элементы 0, gap, 2·gap, ... образуют одну, элементы 1, gap+1, 2·gap+1, ... другую, и так далее. Insertion sort применяется к каждой такой подпоследовательности отдельно (реализовано не отдельным циклом, а одним проходом с шагом gap — что эквивалентно). После обработки всех подпоследовательностей массив называют "gap-отсортированным": в нём нет пары элементов на расстоянии gap друг от друга не по порядку. Затем gap уменьшается (классическая последовательность Кнута: gap = n/2, n/4, ..., 1), и процесс повторяется. Инвариант на входе в каждый проход: массив уже (предыдущий gap)-отсортирован — а значит инверсий на больших расстояниях в нём уже не осталось, и текущему проходу нужно устранять только более мелкую неупорядоченность.For a given gap, the array is conceptually split into gap independent subsequences — elements 0, gap, 2·gap, ... form one, elements 1, gap+1, 2·gap+1, ... another, and so on. Insertion sort is applied to each such subsequence separately (implemented not as a separate loop but as a single pass with stride gap — which is equivalent). After all subsequences are processed, the array is called "gap-sorted": it has no pair of elements gap apart that's out of order. The gap is then shrunk (the classic Knuth sequence: gap = n/2, n/4, ..., 1), and the process repeats. The invariant entering each pass: the array is already (previous gap)-sorted — so long-distance inversions are already gone, and the current pass only needs to fix finer-grained disorder.

void shell_sort(std::vector<int>& a) {
    int n = (int)a.size();
    for (int gap = n / 2; gap > 0; gap /= 2) {
        // insertion sort с шагом gap вместо шага 1// insertion sort with stride gap instead of stride 1
        for (int i = gap; i < n; ++i) {
            int key = a[i];
            int j = i;
            while (j >= gap && a[j - gap] > key) {
                a[j] = a[j - gap];
                j -= gap;
            }
            a[j] = key;
        }
    }
}

Столбики окрашены по остатку индекса от текущего gap — каждый цвет своя подпоследовательность. Жёлтый — текущий "key" внутри своей подпоследовательности, сдвигающийся влево на gap позиций за раз.Bars are colored by index modulo the current gap — each color is its own subsequence. Yellow is the current "key" within its subsequence, shifting left by gap positions at a time.

В отличие от большинства алгоритмов этого раздела, у shell sort нет единой формулы сложности — она зависит от того, как убывает gap. Последовательность Шелла (n/2, n/4, ..., 1, как в коде выше) даёт Θ(n²) в худшем случае — не лучше обычного insertion sort асимптотически, хотя на практике заметно быстрее из-за меньшего числа сдвигов. Последовательность Кнута (3^k - 1)/2 даёт O(n^1.5); последовательность Прэтта (числа вида 2^p·3^q) — O(n log² n); лучшие известные последовательности (Циура) дают эмпирически ~O(n^1.3) без строгого доказательства верхней границы. Это делает shell sort редким примером алгоритма, чья асимптотика — предмет открытого исследования, а не решённая теорема.Unlike most algorithms in this section, shell sort has no single complexity formula — it depends on how the gap shrinks. Shell's original sequence (n/2, n/4, ..., 1, as in the code above) gives Θ(n²) worst case — no better than plain insertion sort asymptotically, though noticeably faster in practice due to fewer shifts. Knuth's sequence (3^k - 1)/2 gives O(n^1.5); Pratt's sequence (numbers of the form 2^p·3^q) gives O(n log² n); the best known sequences (Ciura's) give an empirical ~O(n^1.3) without a proven tight upper bound. This makes shell sort a rare example of an algorithm whose asymptotics are a subject of open research rather than a settled theorem.