Изменения
Нет описания правки
* '''Шаг 1.''' Разобьем массив на списки элементов, отстающих друг от друга на <tex>h_i</tex>. Таких списков будет <tex>h_i</tex>.
* '''Шаг 2.''' Отсортируем элементы каждого списка [[Сортировка вставками|сортировкой вставками]].
* '''Шаг 3.''' Объединим списки обратно в массив. Уменьшим <tex>i</tex>, если . Если <tex>i</tex> неотрицательно - вернемся к шагу 1.
* Конец.
Доказательство данных теоремы и леммы изложено в первой книге предложенных предложенной к прочтению.
В первом приближении функция <tex>f(n,h)</tex> равна <tex> (\sqrt{\pi}/8)n^{3/2}h^{1/2}</tex>. Следовательно <tex>D</tex> для двух проходов будет примерно пропорционально <tex>2N^2/h+\sqrt{\pi N^3h}</tex>. Поэтому наилучшее значение <tex>h</tex> равно приблизительно <tex>\sqrt[3]{16N/ {\pi}} \approx 1.72\sqrt[3]{N}</tex>, при таком выборе <tex>h</tex> среднее время сортировка сортировки пропорционально <tex>N^{5/3}</tex>.
Таким образом, применяя метод Шелла и используя всего 2 прохода, можно сократить время по сравнению с методом простых вставок с <tex>O(N^2)</tex> до <tex>O(N^{1.(6)})</tex>.
