По своей сути сортировка Шелла является модификацией сортировки вставками, о которой мы рассказывали в предыдущей статье. Коротко напомним. При сортировке вставкой массив проходится слева направо. Берём элемент и ищем, куда его можно вставить в левой части массива так, чтобы слева находилось меньшее число, а справа — большее. И делаем так с каждым последующим элементом. Сложность алгоритма вставками в худшем случае равняется O(n²).

«Что, если мы будем идти не по всему массиву, а будем выполнять сортировку вставками в подмассивах, которые представляют собой элементы исходного массива, взятые с определённым интервалом?» — наверное, подумал Дональд Шелл и в 1959 году опубликовал эту идею. 

Попробуем её продемонстрировать. Допустим, у нас есть массив элементов:

(а₁, а₂, а₃, а₄, а₅, а₆, а₇, а₈, а₉, а₁₀, а₁₁)

Применим алгоритм сортировки вставками к подмассиву, состоящему из каждого 5-го элемента, выглядеть он будет так:

(а₁, а₆, а₁₁)

Сохраняем результат сортировки в основном массиве. И теперь, с тем же интервалом между элементами, сдвигаемся на элемент вправо и сортируем подмассив (а₂, а₇), затем то же самое для (а₃, а₈). И делаем так, пока не дойдём до конца массива.

Далее, возьмём подмассив из каждого 3-го элемента:

(а₁, а₄, а₇, а₁₀)

Опять сохраняем результат сортировки в основном массиве. Затем, уже привычным движением сдвигаемся на один элемент вправо, получаем подмассив:

(а₂, а₅, а₈, а₁₁)

Сортируем так и далее.

В конце, выполняем обычную сортировку вставками для всего массива, который уже является частично отсортированным. Вот и вся идея.

А теперь самое интересное: сложность алгоритма будет зависеть от того, какие интервалы выбрать между элементами для выделения подмассивов. Вариантов много, перечислим самые популярные:

Последовательность Шелла

Первый интервал между элементами равен длине массива. На каждом следующем шаге интервал уменьшается вдвое. Вычислительная сложность в худшем случае — O(n²).

Последовательность Хиббарда

Берутся конкретные расстояния между элементами, вычисляемые по формуле 2^k-1. В худшем случае получаем O(n^1.5).

Последовательность Седжвика

Формула сложная и здесь не поместится. Вычислительная сложность в худшем случае — O(n^4/3).

Последовательность Пратта

Все произведения степеней двойки и тройки. Вычислительная сложность в худшем случае — O(n log²n).

Последовательность Циура

Считается лучшим предложенным рядом. Получена экспериментально, и данных о вычислительной сложности нет. Полагаем, она должна быть близка к O(n log n).

Вот почему мы не можем отнести этот алгоритм ни к простым, ни к сложным. Его вычислительная сложность сильно зависит от размера массива и от выбранной последовательности. А выбрать или рассчитать последовательность саму — дело не самое простое!

Узнать больше о других видах сортировок вы можете из материалов блога:

• Разбираем простые сортировки на примерах.
• Разбираем простые сортировки. Пузырьковая сортировка.
• Разбираем пирамидальную сортировку.