Сортировка Шелла называется так по имени своего автора, Дональда Л. Шелла (Donald Lewis Shell). Дональд Л. Шелл описал свой метод сортировки 28 июля1959года. Данный метод классифицируется как слияние с обменом; часто называется также сортировкой с убывающим шагом. Однако это название закрепилось, вероятно, также потому, что действие этого метода часто иллюстрируется рядами морских раковин, перекрывающих друг друга (по-английски "shell" — "раковина"). Общая идея заимствована из сортировки вставками и основывается на уменьшении шагов. Шаг — расстояние между сортируемыми элементами на конкретном этапе сортировки. Рассмотрим диаграмму на следующем рисунке. Сначала сортируются все элементы, отстоящие друг от друга на три по¬зиции. Затем сортируются элементы, расположенные на расстоянии двух позиций. Наконец, сортируются все соседние элементы. То, что этот метод дает хорошие результаты, или даже то, что он вообще сортирует массив, увидеть не так просто. Тем не менее, это верно. Каждый проход сортировки распространяется на относительно небольшое количество элементов либо на элемен¬ты, расположенные уже в относительном порядке. Поэтому сортировка Шелла эффективна, а каждый проход повышает упорядоченность.
Рис. 1.  Проход 1
Рис. 2.  Проход 2
Рис. 3.  Проход 3
Результат a b с d e f
Конкретная последовательность шагов может быть и другой. Единственное правило состоит в том, чтобы последний шаг был равен 1. Например, такая последовательность:
9, 5, 3, 2, 1
дает хорошие результаты и применяется в показанной здесь реализации сортировки Шелла. Следует избегать последовательностей, которые являются степенями числа 2 — по математически сложным соображениям они уменьшают эффективность сортировки (но сортировка по-прежнему работает!).
/*   Сортировка Шелла.   */
void shell(char  *items,   int count)
register   int   i,   j,   gap,   k; char  x,   a[5];
a[0]=9; a[l]=5; a[2]=3; a[3]=2; a[4]=l;
for(k=0; к < 5; k++) { 
gap = a[k];
for(i=gap; i < count; ++i) { 
x = items[i];
for(j=i-gap; (x < items [j]) && (j >= 0); j=j-gap)
items[j+gap] = items [j]; items[j+gap] = x;
}
}
}
Mожно заметить, что внутренний цикл for имеет два условия проверки. Очевидно, что сравнение x<items[j] необходимо для процесса сортировки. Выражение j>=0 предотвращает выход за границу массива items. Эти дополнительные проверки в некоторой степени понижают производительность сортировки Шелла.
В слегка модифицированных версиях данного метода сортировки применяются специальные элементы массива, называемые сигнальными меткими. Они не принадлежат к собственно сортируемому массиву, а содержат специальные значения, соответствующие наименьшему возможному и наибольшему возможному элементам. Это устраняет необходимость проверки выхода за границы массива. Однако применение сигнальных меток элементов требует конкретной информации о сортируемых данных что уменьшает универсальность функции сортировки.
Анализ сортировки Шелла связан с очень сложными математическими задачами. Вообще говоря, время сортировки Шелла зависит от последовательности шагов.(Впрочем, минимум равен, конечно, nlog2n.) Оптимальная последовательность не известна до сих пор.
Дональд Кнут исследовал различные последовательности (не забыв и последовательность Фибоначчи). Фактически он пришел к выводу, что в определении наилучшей последовательности есть какое-то колдовство". В 1969 г. Воган Пратт обнаружил, что если все шаги выбираются из множества чисел вида 2з3q, меньших n, то время работы будет порядка n(logn)2. А.А. Папернов и Г.В. Стасевич в 1965 г. доказали, что максимальное время сортировки Шелла не превосходит 0(n1.5), причем уменьшить показатель 1.5 нельзя. Большое число экспериментов с сортировкой Шелла провели Джеймс Петерсон и Дэвид Л. Рассел в Стэнфордском университете в 1971 г.
Они пытались определить среднее число перемещений при 100<n<250000 для последовательности шагов 2k-1. Наиболее подходящими формулами оказались 1.21n1.26 и .39n(ln n)-2.33nln n. Но при изменении диапазона n оказалось, что коэффициенты в представлении степенной функцией практически не изменяются, а коэффициенты в логарифмическом представлении изменяются довольно резко. Поэтому естественно предположить, что именно степенная функция описывает истинное асимптотическое поведение сортировки Шелла. Время сортировки пропорционально n1.2 при сортировке п элементов. А это уже существенное улучшение по сравнению с сортировками порядка n2. Далее на рисунке показаны графики функций n2 и n1.2. Тем не менее, не стоит чрезмерно восхищаться сортировкой Шелла — быстрая сортировка еще лучше.