Сортировка Шелла

В 1959 году Д. Шеллом было предложено усовершенствование сортировки с помощью метода прямого включения. Иллюстрация его сортировки с начальным шагом, равным 4, представлена на нижеследующем рисунке.

Сначала отдельно группируются и в группах сортируются элементы, отстоящие друг от друга на расстоянии 4. Такой процесс называется четверной сортировкой. В нашем примере 8 элементов, и каждая группа состоит из двух элементов, то есть 1-й и 5-й элементы, 2-й и 6-й, 3-й и 7-й и, наконец, 4-й и 8-й элементы. После четверной сортировки элементы перегруппировываются - теперь каждый элемент группы отстоит от другого на 2 позиции - и вновь сортируются. Это называется двойной сортировкой. И наконец, на третьем проходе идет обычная или одинарная сортировка.

На первый взгляд можно засомневаться: если необходимо несколько процессов сортировки, причем в каждый включаются все элементы, то не добавят ли они больше работы, чем сэкономят? Однако, на каждом этапе либо сортируется относительно мало элементов, либо элементы уже довольно хорошо упорядочены и требуют сравнительно немного перестановок.

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

Приводимый ниже алгоритм не ориентирован на некую определенную последовательность расстояний и использует метод прямой вставки с условным переходом.

При использовании метода барьера каждая из сортировок нуждается в постановке своего собственного барьера, поэтому приходится расширять массив с [0.. N ] до [- h 1.. N ].

Не доказано, какие расстояния дают наилучший результат, но они не должны быть множителями один другого. Д. Кнут предлагает такую последовательность шагов h (в обратном порядке): 1, 3, 7, 15, 31, …

То есть:
h m = 2 h m -1 + 1, а количество шагов
t = (log 2 n) - 1.

При такой организации алгоритма его эффективность имеет порядок O (n 1,2)