Идея алгоритма состоит в обмене элементов, расположенных не только рядом, как в сортировке методом вставок, но и далеко друг от друга, что значительно сокращает общее число операций перемещения элементов.
Для примера возьмем файл из 16 элементов. Сначала просматриваются пары с шагом 8. Это пары элементов 1−9, 2−10, 3−11, 4−12, 5−13, 6−14, 7−15, 8−16. Если значения элементов в паре не упорядочены по возрастанию, то элементы меняются местами. Назовем этот этап 8-сортировкой. Следующий этап — 4-сортировка, на котором элементы в файле делятся на четверки: 1−5-9−13, 2−6-10−14, 3−7-11−15, 4−8-12−16. Выполняется сортировка в каждой четверке.
Следующий этап — 2-сортировка, когда элементы в файле делятся на 2 группы по 8: 1−3-5−7-9−11−13−15 и 2−4-6−8-10−12−14−16. Выполняется сортировка в каждой восьмерке. Наконец весь файл упорядочивается методом вставок. Поскольку дальние элементы уже переместились на свое место или находятся вблизи от него, этот этап будет значительно менее трудоемким, чем при сортировке вставками без предварительных «дальних» обменов.
Анализ алгоритма сортировки Шелла Время выполнения сортировки пропорционально n1.2. Эта зависимость значительно лучше квадратичной зависимости n2, которой подчиняется большинство простых алгоритмов сортировки.
Пример реализации.
Pascal.
procedure sort_shell (var a: array of word);
var.
bis, i, j, k: longint;
h:word;
begin.
bis:=high (a);
k:=bis shr 1;
While k>0 do.
Begin.
For i:=0 To bis-k do.
begin.
j:=i;
While (j>=0) And (a[j]>a[j+k]) do.
begin.
h:=a[j];
a[j]: =a[j+k];
a[j+k]: =h;
dec (j, k);
end;
end;
k:=k shr 1;
End;
End;
