Сортировка Шелла является усовершенствованным методом простых вставок. Метод предложен Д.Шеллом в 1959 г. и назван именем автора. Характерным для данного метода является то, что сначала рассматриваются отдаленные, а затем – близкорасположенные записи. Каждый проход в этом случае характеризуется некоторым смещением h для сортируемых записей – интервал, который разделяет сравниваемые записи.

Другими словами, каждая запись отстоит от предыдущей записи на h позиций. Часто используют последовательность смещений 8, 4, 2, 1. Последнее смещение всегда h=1.

После первого прохода элементы объединяются в группы с элементами, которые отстоят друг от друга на две позиции, и снова сортируются. Процесс завершается проходом, во время которого сортируются все элементы рассматриваемого массива в той последовательности, которая получена после последнего прохода, с помощью обычной сортировки.

В результате имеется упорядоченный массив. Каждый проход в данном методе использует результаты предыдущего прохода.

Данный метод достаточно легко программируется. Он эффективен при умеренно больших N (N<=1000).