Shell Sort

Проблема

Сортировка вставками эффективна на почти отсортированных данных, но медленна, когда маленький элемент находится далеко от своего места - его приходится сдвигать через все промежуточные позиции по одной. На случайном массиве это создаёт много «мелких шагов» там, где нужен один большой прыжок.

Решение

Алгоритм задаёт последовательность убывающих промежутков (gap), например n/2, n/4, ..., 1. На каждом шаге он выполняет сортировку вставками, но сравнивает не соседние элементы, а элементы, отстоящие друг от друга на текущий gap - это позволяет далёким элементам быстро «перепрыгнуть» на нужную сторону массива. Когда gap становится равным 1, выполняется обычная сортировка вставками, но к этому моменту массив уже почти упорядочен, поэтому она проходит быстро.

Как это работает

Возьмём массив [8, 3, 6, 1, 5, 2, 7, 4] (n=8). Сортировка Шелла начинает с gap = 4 и делит массив на 4 подпоследовательности: [8,5], [3,2], [6,7], [1,4]. Каждая сортируется вставками независимо. После первого прохода массив выглядит как [5, 2, 6, 1, 8, 3, 7, 4] - ни одна пара ещё не стоит правильно относительно соседа, но дальние элементы уже близко к своим позициям. Это главная идея: крупные прыжки сначала.

Почему обычная сортировка вставками медленна на случайных данных? Из-за «черепах» - маленьких элементов, попавших в правую часть массива. Элемент 1 в позиции 7 при вставками сдвигается на одну позицию влево за проход - значит, ему нужно 7 проходов, чтобы добраться до начала. Сортировка Шелла убивает черепах за один проход с большим gap: при gap=4 элемент 1 сразу перепрыгивает через 4 позиции вместо одной. Именно устранение черепах объясняет ускорение.

Последовательность gap n/2, n/4, ..., 1 даёт O(log n) проходов. Для n=8 это проходы с gap 4, 2, 1 - всего три. На каждом проходе алгоритм выполняет сортировку вставками для подпоследовательностей длиной n/gap. Ключевое наблюдение: к моменту финального прохода с gap=1 массив уже почти отсортирован - предыдущие проходы разместили все элементы близко от их итоговых позиций. Сортировка вставками на почти отсортированном массиве работает за O(n), а не за O(n²).

Почему средняя сложность ~O(n^1.3), а не O(n log n)? Дело в проходах с промежуточными значениями gap. При gap=2 алгоритм обрабатывает подпоследовательности длиной n/2, и каждая занимает до O((n/2)²) в худшем случае. Точный анализ зависит от выбранной последовательности gap и остаётся открытой математической задачей для некоторых вариантов. Простейшая последовательность Шелла (n/2, n/4, ...) даёт O(n²) в худшем случае; более умные последовательности снижают это до O(n^1.3) и лучше.

Почему сортировка Шелла неустойчива (unstable)? Возьмём [2a, 2b, 1], где 2a и 2b - равные значения. При gap=2 алгоритм сравнивает элементы на позициях 0 и 2: 2a и 1. Поскольку 2a > 1, происходит обмен: [1, 2b, 2a]. Теперь 2b стоит левее 2a, хотя исходно было наоборот. Прыжок через равный элемент - корень проблемы: в отличие от сортировки вставками, где элемент сдвигается по одной позиции и никогда не перепрыгивает равных, здесь gap позволяет перескочить через них.

Сравнение с сортировкой вставками раскрывает, что именно ускоряет алгоритм. Оба метода в финале делают одно и то же - сортировку вставками с gap=1. Разница в том, что Shell sort заранее подготавливает данные: несколько проходов с большими gap гарантируют, что к финальному проходу никакой элемент не отстоит от своего места более чем на несколько позиций. На случайном массиве размером n=1000 insertion sort делает в среднем ~250 000 сдвигов, Shell sort с последовательностью n/2 - около ~11 000 сдвигов.

Сравнение с merge sort показывает главный компромисс. Merge sort гарантирует O(n log n) в любом случае и устойчива - но требует O(n) дополнительной памяти и рекурсии глубиной O(log n). Сортировка Шелла работает на месте без рекурсии: весь код умещается в два вложенных цикла и не выделяет ни одного байта сверх O(1). На массивах от 20 до ~500 элементов Shell sort в практических тестах нередко обгоняет merge sort за счёт отсутствия оверхеда на аллокацию и рекурсивные вызовы.

Нюансы выбора

Главная ниша сортировки Шелла - ограниченная среда: встроенные системы и ядра ОС, где запрещено динамическое выделение памяти или глубокая рекурсия. Merge sort требует O(n) дополнительной памяти - недопустимо при стеке в 2-4 KB на микроконтроллере. Quicksort при глубокой рекурсии может переполнить стек на вырожденных входных данных. Shell sort решает обе проблемы: O(1) памяти и ноль рекурсии - конкретный промышленный пример такого выбора смотри в разделе «Примеры в коде».

Средние массивы (от ~20 до ~500 элементов) - ещё одна подходящая ниша. На этом диапазоне сортировка Шелла стабильно опережает bubble sort и insertion sort, при этом не несёт оверхеда рекурсии и аллокации merge sort. Quicksort асимптотически быстрее, но его худший случай O(n²) возникает на уже отсортированных данных при наивном выборе pivot. Shell sort лишён этого риска - у неё нет вырожденного входа в смысле катастрофического замедления.

Shell sort подходит, когда устойчивость не нужна. Если порядок равных элементов после сортировки не важен - алгоритм полностью справляется. Как только появляется требование «сохранить исходный порядок среди равных» (например, сортировка таблицы по нескольким полям) - нужен Timsort, merge sort или insertion sort, все из которых устойчивы. Смена алгоритма в этом случае обязательна, не опциональна.

Три оси выбора помогают принять решение: память, рекурсия, скорость. По памяти Shell sort выигрывает у merge sort (O(1) против O(n)). По рекурсии выигрывает у quicksort и merge sort - итеративный по построению. По скорости уступает обоим на больших массивах (n > 500), где O(n log n) начинает решать. Выбирать Shell sort, когда первые два критерия важнее третьего - это именно среда выполнения задаёт приоритеты.

Никогда для больших данных (n > 1000). При таких размерах разрыв между ~O(n^1.3) и O(n log n) становится ощутимым: на n=10 000 merge sort делает ~130 000 операций, Shell sort с простой последовательностью - порядка ~500 000. Кэш-промахи от прыжков через gap ещё ухудшают картину на современных CPU. Для больших массивов - quicksort, merge sort или Timsort без исключений.

Как строительный блок: идея убывающих расстояний между сравниваемыми элементами влияет на другие алгоритмы. Comb sort применяет ту же убывающую последовательность gap к пузырьковой сортировке вместо вставками, добиваясь схожего ускорения. Сам принцип «сначала устранить дальние несоответствия, потом точно настроить соседей» встречается в библиотечной сортировке и некоторых вариантах сортировки вставками с бинарным поиском позиции.

Примеры в коде

uClibc - наиболее известный пример промышленного применения. Это стандартная C-библиотека для встраиваемых Linux-систем (роутеры, NAS-устройства, промышленные контроллеры). Её qsort() реализован через Shell sort, а не quicksort: причина - отсутствие рекурсии и гарантированный O(1) стек. В прошивке роутера или промышленного ПЛК переполнение стека во время сортировки неприемлемо, а Shell sort это исключает по конструкции.

Linux kernel использовал Shell sort в ряде внутренних компонентов. В частности, ранние версии lib/sort.c содержали реализацию Shell sort для сортировки небольших внутренних структур ядра. Позднее его заменили на Heapsort (lib/sort.c, начиная с версий 2.6.x) - тот же O(1) памяти и отсутствие рекурсии, но гарантированный O(n log n) вместо ~O(n^1.3). Переход отражает стандартную эволюцию: Shell sort как промежуточный шаг перед более строгой гарантией.

История последовательностей gap - отдельная исследовательская область. Дональд Шелл в 1959 году предложил простейшую n/2. Дональд Кнут в 1973 году показал, что последовательность 1, 4, 13, 40, 121, ... (h = 3h+1) даёт O(n^1.5). Роберт Седжвик в 1986 году нашёл последовательность, дающую O(n^4/3) в худшем случае. Чистая задача "найти оптимальную последовательность gap для Shell sort" до сих пор остаётся математически открытой - это редкий пример алгоритма, оптимальность которого не доказана.

Comb sort (1980, Влodek Dobosiewicz) - прямой духовный потомок Shell sort. Вместо применения убывающего gap к сортировке вставками comb sort применяет его к сортировке пузырьком: сравнивает и переставляет элементы на расстоянии gap, затем уменьшает gap по фактору ~1.3. Практическая скорость сопоставима с Shell sort, реализация ещё проще - два вложенных цикла с одним условием. Оба алгоритма решают одну и ту же проблему черепах одним и тем же принципом, но от разных базовых алгоритмов.

Где Shell sort не встречается? В стандартных библиотеках языков общего назначения - нигде. Python (list.sort) - Timsort. Java (Arrays.sort для объектов) - Timsort. C++ (std::sort) - introsort. Go (sort.Slice) - pdqsort. Rust (slice::sort_unstable) - pdqsort. Причина: все эти языки работают в средах с достаточным стеком и динамической памятью, где O(n log n) с гарантией важнее экономии на аллокации. Shell sort живёт там, где ресурсов мало - и именно там он незаменим.

Когда применять

• Когда нужна сортировка на месте лучше, чем O(n²), но без накладных расходов на рекурсию или дополнительную память merge sort.
• Для встроенных систем и библиотек, где важна простота кода при разумной производительности на средних объёмах данных.

Примеры из практики

• uClibc (стандартная библиотека C для встраиваемых систем) использует сортировку Шелла для qsort() из-за её компактного кода и хорошей производительности без рекурсии.
• Ранние версии Linux kernel применяли сортировку Шелла в некоторых внутренних утилитах, где нужна была простая сортировка на месте без выделения памяти.