В 1959 г. Д. Шеллом было предложено усовершенствование сортировки с помощью прямого включения. Сам метод сортировки объясняется и демонстрируется на стандартном примере (рис. 3.5). Сначала отдельно группируются и сортируются элементы, отстоящие друг от друга на 4 позиции. Такой процесс называется четвертной сортировкой. В нашем примере восемь элементов каждая группа состоит ровно из двух элементов. После первого прохода элементы перегруппировываются — теперь каждый элемент группы отстоит от другого на две позиции — и вновь сортируются. Это называется двойной сортировкой. Наконец, на третьем проходе идет обычная сортировка [1,3,9,10,13].
Сначала может показаться, что необходимость нескольких проходов сортировки, в каждом из которых участвуют все элементы, потребует большего количества машинных ресурсов, чем обычная сортировка. Однако на каждом этапе либо сортируется относительно мало элементов, либо элементы уже довольно хорошо упорядочены и требуется сравнительно немного перестановок.
Ясно, что такой метод в результате дает упорядоченный массив, и, конечно же, сразу видно, что каждый проход от предыдущих только выигрывает (так как каждая /-сортировка объединяет две группы, уже отсортированные 2i-сортировкой). Очевидно так же, что расстояния в группах можно уменьшать по-разному, лишь бы последнее было единичным, ведь в самом плохом случае последний проход и сделает всю работу.