Сортировку Шелла придумал Дональд Л. Шелл. Ее необычность состоит в том, что она рассматривает весь список как совокупность перемешанных подсписков. На первом шаге эти подсписки представляют собой просто пары элементов. На втором шаге в каждой группе по четыре элемента. При повторении процесса число элементов в каждом подсписке увеличивается, а число подсписков, соответственно, падает. На рисунке ниже изображены подсписки, которыми можно воспользоваться при сортировке списка из 16 элементов.


    На рисунке (а) изображены восемь подсписков, по два элемента в каждом, в которых первый подсписок содержит первый и девятый элементы, второй подсписок - второй и десятый элементы, и так далее. На рисунке (б) мы видим уже четыре подсписка по четыре элемента в каждом. Первый подсписок на этот раз содержит первый, пятый, девятый и тринадцатый элементы. Второй подсписок состоит из второго, шестого, десятого и четырнадцатого элементов. На рисунке (в) показаны два подсписка, состоящие из элементов с нечетными и четными номерами соответственно. На рисунке (г) мы вновь возвращаемся к одному списку.
    Сортировка подсписков выполняется путем однократного применения сортировки вставками. В результате мы получаем следующий алгоритм:

ShellSort(list, N)
list			сортируемый список элементов
N			число элементов в списке

passes = [log_2 N]
while (passes >= 1) do
	increment = 2^passes-1
	for start = 1 to increment do
		InsertionSort(list, N, start, increment)
	end for
	passes = passes - 1
end while