Метод Шелла (сортировка с убывающем шагом)

Записи R₁,…, R_N перемещаются на том же месте. После завершения сортировки их ключи будут упорядочены: К₁ £ … £К _N. Для управления процессом сортировки используются вспомогательная последовательность шагов h _t h _t-1,…, h ₁, где h ₁=1. Правильно выбрав эти приращения, можно значительно сократить время сортировки. При t = 1 алгоритм сводится к алгоритму простой вставки.

(Цикл по р) Выполнить шаг Ш2 при р = t, t –1, …, 1, после чего завершить алгоритм.

(Цикл по j). Установить h:= h_t, и выполнить шаги Ш3 – Ш6 при h < j £ N. (для сортировки элементов, отстоящих друг от друга на h позиций, воспользуемся простыми вставками и в результате получим К _t £ К _{t + h} при 1£ i £ N – h.

(Установить i, К, R). Установить i = j – h, К=К _j , R = R _j .

(Сравнить К, К _i ) Если К>=К _i , то перейти к шагу Ш6.

(Переместить R_i , уменьшить i). Установить R _{i + h} = R _i , затем i =i– h. Если i > 0, то возвратиться к шагу Ш4.

(R на место R_{i+ h} ) Установить R_{i+ h} = R.

На выбор шагов h_t, h_t-1,…, h₁ значительно влияет условие делимости:

h_s+1 mod h_s = 0, при t > s >= 1.

Применяя метод Шелла со всего двумя шагами, можно существенно сократить время по сравнению с простыми вставками с 0(N²) до 0(N^1.667). Если использовать больше шагов, то можно добиться лучших результатов.