Выбор длины промежутков

Среднее время работы алгоритма зависит от длин промежутков — d, на которых будут находиться сортируемые элементы исходного массива ёмкостью N на каждом шаге алгоритма. Существует несколько подходов к выбору этих значений:

● первоначально используемая Шеллом последовательность длин промежутков: в худшем случае, сложность алгоритма составит cN 2;

● предложенная Хиббардом последовательность: все значения ; такая последовательность шагов приводит к алгоритму сложностью O (N 3 / 2);

● предложенная Седжвиком последовательность: , если i четное и , если i нечетное. При использовании таких приращений средняя сложность алгоритма составляет: O (n 7 / 6), а в худшем случае порядка O (n 4 / 3). При использовании формулы Седжвика следует остановиться на значении inc[s-1], если 3*inc[s] > size.[1];

● предложенная Праттом последовательность: все значения ; в таком случае сложность алгоритма составляет O (N (logN)2);

● эмпирическая последовательность Марцина Циура (последовательность A102549 в OEIS): ; является одной из лучших для сортировки массива ёмкостью приблизительно до 4000 элементов.[2];

● эмпирическая последовательность, основанная на числах Фибоначчи: ;

● все значения [ источник не указан 770 дней ], ; такая последовательность шагов приводит к алгоритму сложностью O (N 3 / 2).