Shellsort

Алгоритм сортировки, который использует несколько интервалов сравнения

Shellsort

Shellsort с пробелами 23, 10, 4, 1 в действии
Класс	Алгоритм сортировки
Структура данных	Массив
наихудший случай производительность	O (n) (наихудшая известная последовательность разрывов наихудшего случая). O (n logn) (наиболее известная последовательность разрывов наихудшего случая)
Лучшая ситуация производительность	O (n log n) (большинство последовательностей пропусков). O (n logn) (наиболее известная наихудшая- последовательность пробелов)
Средняя производительность	зависит от последовательности пробелов
Худший случай сложность пространства	О (n) всего, O (1) вспомогательная

Замена пар элементов на последовательных шагах Shellsort с промежутками 5, 3, 1

Shellsort, также известная как Shell sort или метод Shell, является на месте сравнительная сортировка. Это можно рассматривать как обобщение сортировки путем обмена (пузырьковая сортировка ) или сортировки путем вставки (сортировка вставкой ). Метод начинается с сортировки пар элементов на большом расстоянии друг от друга, а затем постепенного уменьшения разрыва между сравниваемыми элементами. Начав с удаленных друг от друга элементов, он может перемещать некоторые неуместные элементы на место быстрее, чем простой обмен ближайшими соседями. Дональд Шелл опубликовал первую версию такого рода в 1959 году. Время работы Shellsort сильно зависит от используемой им последовательности пропусков. Для многих практических вариантов определение их временной сложности остается открытой проблемой.

• 1 Описание
• 2 Псевдокод
• 3 Последовательности пробелов
• 4 Вычислительная сложность
• 5 Приложения
• 6 См. Также
• 7 Ссылки
• 8 Библиография
• 9 Внешние ссылки

Shellsort - это оптимизация сортировки вставкой, которая позволяет обмен предметами, находящимися далеко друг от друга. Идея состоит в том, чтобы организовать список элементов таким образом, чтобы начиная с любого элемента, взяв каждый h-й элемент, получился отсортированный список. Такой список называется h-отсортированным. Его также можно представить как h чередующихся списков, каждый из которых отсортирован индивидуально. Начало с больших значений h позволяет элементам перемещаться на большие расстояния в исходном списке, быстро уменьшая большое количество беспорядка и оставляя меньше работы для небольших шагов h-сортировки. Если затем список отсортирован по k для некоторого меньшего целого числа k, то список останется отсортированным по h. Следуя этой идее убывающей последовательности значений h, оканчивающихся на 1, гарантированно останется отсортированный список в конце.

В упрощенных терминах это означает, что если у нас есть массив из 1024 чисел, наш первый пробел (h) может быть 512. Затем мы просматриваем список, сравнивая каждый элемент в первой половине с элементом во второй половине. Наш второй пробел (k) равен 256, что разбивает массив на четыре раздела (начиная с 0,256,512,768), и мы убеждаемся, что первые элементы в каждом разделе отсортированы относительно друг друга, затем второй элемент в каждом разделе и т. Д.. На практике последовательность пропусков может быть любой, но последний пробел всегда равен 1 для завершения сортировки (фактически завершение обычной сортировки вставкой).

Пример выполнения Shellsort с пробелами 5, 3 и 1 показан ниже.

	a1	a2	a3	a4	a5	a6	a7	a8	a9	a10	a11	a12
Входные данные	62	83	18	53	07	17	95	86	47	69	25	28
После 5-сортировки	17	28	18	47	07	25	83	86	53	69	62	95
После 3-сортировки	17	07	18	47	28	25	69	62	53	83	86	95
После 1-сортировки	07	17	18	25	28	47	53	62	69	83	86	95

Первый проход, 5-сортировка, выполняет сортировку вставкой для пяти отдельных подмассивов (a 1, a 6, a 11), (a 2, a 7, a 12), (a 3, a 8), (a 4, a 9), (a 5, a 10). Например, он изменяет подмассив (a 1, a 6, a 11) с (62, 17, 25) на (17, 25, 62). Следующий проход, 3-сортировка, выполняет сортировку вставкой на трех подмассивах (a 1, a 4, a 7, a 10), (a 2, a 5, a 8, a 11), (a 3, a 6, a 9, a 12). Последний проход, 1-сортировка, представляет собой обычную сортировку вставкой всего массива (a 1,..., a 12).

Как показывает пример, подмассивы, с которыми работает Shellsort, изначально короткие; позже они стали длиннее, но почти заказаны. В обоих случаях сортировка вставкой работает эффективно.

Shellsort не стабильный : он может изменить относительный порядок элементов с равными значениями. Это алгоритм адаптивной сортировки в том смысле, что он выполняется быстрее, когда входные данные частично отсортированы.

Использование последовательности пробелов Марцина Чиуры с внутренней сортировкой вставкой.

# Сортировать массив a [0... n-1]. gaps = [701, 301, 132, 57, 23, 10, 4, 1] # Начните с наибольшего пробела и уменьшите пробел до 1 foreach (пробел в пробелах) {# Выполните сортировку вставки с пробелами для этого размера пробела. # Первые элементы промежутка a [0..gap-1] уже находятся в порядке промежутка # продолжайте добавлять еще один элемент, пока весь массив не будет отсортирован по промежуткам (i = gap; i < n; i += 1) { # add a[i] to the elements that have been gap sorted # save a[i] in temp and make a hole at position i temp = a[i] # shift earlier gap-sorted elements up until the correct location for a[i] is found for (j = i; j>= gap и a [j - gap ]>temp; j - = gap) {a [j] = a [j - gap]} # поместите temp (исходный a [i]) в его правильное место a [j] = temp}}

Вопрос о том, какую последовательность пропусков использовать, является трудным. Каждая последовательность пробелов, содержащая 1, дает правильную сортировку (так как это делает последний проход обычной сортировкой вставкой); однако свойства полученных таким образом версий Shellsort могут сильно отличаться. Слишком мало пропусков замедляет проходы, а слишком большое количество пропусков приводит к накладным расходам.

В таблице ниже сравнивается большинство предложенных последовательностей разрывов, опубликованных на данный момент. Некоторые из них имеют уменьшающиеся элементы, которые зависят от размера отсортированного массива (N). Другие представляют собой возрастающие бесконечные последовательности, элементы которых меньше N должны использоваться в обратном порядке.

OEIS	Общий термин (k ≥ 1)	Бетонные промежутки	Худший случай. временная сложность	Автор и год публикации
	$\lfloor \; N\; 2\; К\; \rfloor \; \{\backslash \; Displaystyle\; \backslash \; left\; \backslash \; lfloor\; \{\backslash \; frac\; \{N\}\; \{2\; ^\; \{k\}\}\}\; \backslash \; right\; \backslash \; rfloor\}$	$\lfloor \; N\; 2\; \rfloor ,\; \lfloor \; N\; 4\; \rfloor ,\dots ,\; 1\; \{\backslash \; displaystyle\; \backslash \; left\; \backslash \; lfloor\; \{\backslash \; frac\; \{N\}\; \{2\}\}\; \backslash \; right\; \backslash \; rfloor,\; \backslash \; left\; \backslash \; lfloor\; \{\backslash \; frac\; \{N\}\; \{4\}\}\; \backslash \; right\; \backslash \; rfloor,\; \backslash \; ldots,\; 1\}$	$\Theta \; (N\; 2)\; \{\backslash \; displaystyle\; \backslash \; Theta\; \backslash \; left\; (N\; ^\; \{2\}\; \backslash \; right)\}$[например, когда N = 2]	Shell, 1959
	$2\; \lfloor \; N\; 2\; k\; +\; 1\; \rfloor \; +\; 1\; \{\backslash \; displaystyle\; 2\; \backslash \; left\; \backslash \; lfloor\; \{\backslash \; frac\; \{N\}\; \{2\; ^\; \{k\; +\; 1\}\}\; \}\; \backslash \; right\; \backslash \; rfloor\; +1\}$	$2\; \lfloor \; N\; 4\; \rfloor \; +\; 1,\dots ,\; 3,\; 1\; \{\backslash \; displaystyle\; 2\; \backslash \; left\; \backslash \; lfloor\; \{\backslash \; frac\; \{N\}\; \{4\}\}\; \backslash \; right\; \backslash \; rfloor\; +1,\; \backslash \; ldots,\; 3,1\}$	$\Theta \; (N\; 3\; 2)\; \{\backslash \; displaystyle\; \backslash \; Theta\; \backslash \; left\; (N\; ^\; \{\backslash \; frac\; \{3\}\; \{2\}\}\; \backslash \; right)\}$	Франк и Лазарус, 1960
A000225	$2\; k\; -\; 1\; \{\backslash \; displaystyle\; 2\; ^\; \{k\}\; -1\}$	$1,\; 3,\; 7,\; 15,\; 31,\; 63,\dots \; \{\backslash \; displaystyle\; 1,3,7,15,31,63,\; \backslash \; ldots\}$	$\Theta \; (N\; 3\; 2)\; \{\backslash \; displaystyle\; \backslash \; Theta\; \backslash \; left\; (N\; ^\; \{\backslash \; frac\; \{3\}\; \{2\}\}\; \backslash \; right)\}$	Хиббард, 1963
A083318	$2\; к\; +\; 1\; \{\backslash \; displaystyle\; 2\; ^\; \{k\}\; +1\}$с префиксом 1	$1,\; 3,\; 5,\; 9,\; 17,\; 33,\; 65,\dots \; \{\backslash \; displaystyle\; 1,\; 3,5,9,17,33,65,\; \backslash \; ldots\}$	$\Theta \; (N\; 3\; 2)\; \{\backslash \; displaystyle\; \backslash \; Theta\; \backslash \; left\; (N\; ^\; \{\backslash \; frac\; \{3\}\; \{2\}\}\; \backslash \; right)\}$	Папернов и Стасевич, 1965
A003586	Последовательные числа вида $2\; p\; 3\; q\; \{\backslash \; displaystyle\; 2\; ^\; \{p\}\; 3\; ^\; \{q\}\}$(3-гладкие числа)	$1,\; 2,\; 3,\; 4,\; 6,\; 8,\; 9,\; 12,\dots \; \{\backslash \; displaystyle\; 1,2,3,4,6,8,9,12,\; \backslash \; ldots\}$	$\Theta \; (N\; журнал\; 2\; \; N)\; \{\backslash \; displaystyle\; \backslash \; Theta\; \backslash \; left\; (N\; \backslash \; log\; ^\; \{2\}\; N\; \backslash \; right)\}$	Пратт, 1971
A003462	$3\; k\; -\; 1\; 2\; \{\backslash \; displaystyle\; \{\; \backslash \; frac\; \{3\; ^\; \{k\}\; -1\}\; \{2\}\}\}$, не более $\lceil \; N\; 3\; \rceil \; \{\backslash \; displaystyle\; \backslash \; left\; \backslash \; lceil\; \{\backslash \; frac\; \{N\}\; \{3\}\}\; \backslash \; right\; \backslash \; rceil\}$	$1,\; 4,\; 13,\; 40,\; 121,\dots \; \{\backslash \; displaystyle\; 1,4,13,40,121,\; \backslash \; ldots\}$	$\Theta \; (N\; 3\; 2)\; \{\backslash \; displaystyle\; \backslash \; Theta\; \backslash \; left\; (\; N\; ^\; \{\backslash \; frac\; \{3\}\; \{2\}\}\; \backslash \; right)\}$	Knuth, 1973, на основе Pratt, 1971
A036569		$1,\; 3,\; 7,\; 21,\; 48,\; 112,\dots \; \{\backslash \; displaystyle\; 1,3,\; 7,21,48,112,\; \backslash \; ldots\}$	$О\; (N\; 1\; +\; 8\; ln\; \; (5/2)\; ln\; \; (N))\; \{\backslash \; displaystyle\; O\; \backslash \; left\; (N\; ^\; \{1\; +\; \{\backslash \; sqrt\; \{\backslash \; frac\; \{\; 8\; \backslash \; ln\; \backslash \; left\; (5/2\; \backslash \; right)\}\; \{\backslash \; ln\; (N)\}\}\}\}\; \backslash \; right)\}$	Incerpi Sedgewick, 1985, Knuth
A036562	$4\; k\; +\; 3\; \cdot \; 2\; k\; -\; 1\; +\; 1\; \{\backslash \; displaystyle\; 4\; ^\; \{k\}\; +3\; \backslash \; cdot\; 2\; ^\; \{k-1\}\; +1\}$с префиксом 1	$1,\; 8,\; 23,\; 77,\; 281,\dots \; \{\backslash \; displaystyle\; 1,8,23,77,281,\; \backslash \; ldots\}$	$O\; (N\; 4\; 3)\; \{\backslash \; displaystyle\; O\; \backslash \; left\; (N\; ^\; \{\backslash \; fra\; c\; \{4\}\; \{3\}\}\; \backslash \; right)\}$	Седжвик, 1982
A033622	$\{9\; (2\; k\; -\; 2\; k\; 2)\; +\; 1\; k\; четное,\; 8\; \cdot \; 2\; k\; -\; 6\; \cdot \; 2\; (k\; +\; 1)\; /\; 2\; +\; 1\; k\; нечетные\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{cases\}\; 9\; \backslash \; left\; (2\; ^\; \{k\}\; -2\; ^\; \{\backslash \; frac\; \{k\}\; \{2\}\}\; \backslash \; right)\; +\; 1\; k\; \{\backslash \; text\; \{even\; \}\},\; \backslash \backslash \; 8\; \backslash \; cdot\; 2\; ^\; \{k\}\; -6\; \backslash \; cdot\; 2\; ^\; \{(k\; +\; 1)\; /\; 2\}\; +\; 1\; k\; \{\backslash \; text\; \{odd\}\}\; \backslash \; end\; \{cases\}\}\}$	$1,\; 5,\; 19,\; 41,\; 109,\dots \; \{\backslash \; displaystyle\; 1,5,19,41,109,\; \backslash \; ldots\}$	$O\; (N\; 4\; 3)\; \{\backslash \; displaystyle\; O\; \backslash \; left\; (N\; ^\; \{\backslash \; frac\; \{4\}\; \{3\}\}\; \backslash \; right)\}$	Седжвик, 1986
	$hk\; =\; max\; \{\lfloor \; 5\; hk\; -\; 1\; 11\; \rfloor ,\; 1\},\; h\; 0\; =\; N\; \{\backslash \; displaystyle\; h\_\; \{k\}\; =\; \backslash \; max\; \backslash \; left\; \backslash \; \{\backslash \; left\; \backslash \; lfloor\; \{\backslash \; frac\; \{5h\_\; \{k-1\}\}\; \{11\}\}\; \backslash \; right\; \backslash \; rfloor,\; 1\; \backslash \; right\; \backslash \},\; h\_\; \{0\}\; =\; N\}$	$\lfloor \; 5\; N\; 11\; \rfloor ,\; \lfloor \; 5\; 11\; \lfloor \; 5\; N\; 11\; \rfloor \; \rfloor ,\dots ,\; 1\; \{\backslash \; displaystyle\; \backslash \; left\; \backslash \; lfloor\; \{\backslash \; frac\; \{5N\}\; \{11\}\}\; \backslash \; right\; \backslash \; rfloor,\; \backslash \; left\; \backslash \; lfloor\; \{\backslash \; frac\; \{5\}\; \{11\}\}\; \backslash \; left\; \backslash \; lfloor\; \{\backslash \; frac\; \{5N\; \}\; \{11\}\}\; \backslash \; right\; \backslash \; rfloor\; \backslash \; right\; \backslash \; rfloor,\; \backslash \; ldots,\; 1\}$	Неизвестно	Гоннет и Баеза-Йейтс, 1991
A108870	$\lceil \; 1\; 5\; (9\; \cdot \; (9\; 4)\; к\; -\; 1-4)\; \rceil \; \{\backslash \; displaystyle\; \backslash \; left\; \backslash \; lceil\; \{\backslash \; frac\; \{1\}\; \{5\}\}\; \backslash \; left\; (9\; \backslash \; cdot\; \backslash \; left\; (\{\backslash \; frac\; \{9\}\; \{4\; \}\}\; \backslash \; right)\; ^\; \{k-1\}\; -4\; \backslash \; right)\; \backslash \; right\; \backslash \; rceil\}$	$1,\; 4,\; 9,\; 20,\; 46,\; 103,\dots \; \{\backslash \; displaystyle\; 1,4,9,20,46,103,\; \backslash \; ldots\}$	Неизвестно	Токуда, 1992
A102549	Неизвестно (получено экспериментально)	$1,\; 4,\; 10,\; 23,\; 57,\; 132,\; 301,\; 701\; \{\backslash \; displaystyle\; 1,4,10,23,57,132,301,701\}$	Неизвестно	Ciura, 2001

Когда двоичное представление N содержит много последовательных нулей, Shellsort с использованием исходной последовательности пробелов Shell выполняет сравнения Θ (N) в худшем случае. Например, этот случай имеет место для N, равного степени двойки, когда элементы больше и меньше медианы занимают нечетные и четные позиции соответственно, поскольку они сравниваются только на последнем проходе.

Хотя она имеет более высокую сложность, чем O (N log N), которая является оптимальной для сортировки сравнения, версия Пратта поддается сортировочным сетям и имеет ту же асимптотическую сложность ворот, что и Батчер bitonic sorter.

Гоннет и Баеза-Йейтс заметили, что Shellsort в среднем делает наименьшее количество сравнений, когда соотношение последовательных пропусков примерно равно 2,2. Поэтому их последовательность с коэффициентом 2.2 и последовательность Токуды с коэффициентом 2.25 оказываются эффективными. Однако неизвестно, почему это так. Седжвик рекомендует использовать промежутки, которые имеют низкие наибольшие общие делители или попарно взаимно просты.

. Что касается среднего числа сравнений, последовательность Чиуры имеет наиболее известную производительность; промежутки от 701 не были определены, но последовательность может быть расширена в соответствии с рекурсивной формулой $hk\; =\; \lfloor \; 2.25\; hk\; -\; 1\; \rfloor \; \{\backslash \; displaystyle\; h\_\; \{k\}\; =\; \backslash \; lfloor\; 2.25h\_\; \{k-1\}\; \backslash \; rfloor\}$.

Последовательность Токуды, определяемая простой формулой $hk\; =\; \lceil \; hk\; \prime \; \rceil \; \{\backslash \; displaystyle\; h\_\; \{k\}\; =\; \backslash \; lceil\; h\; \text{'}\_\; \{k\}\; \backslash \; rceil\}$, где $hk\; \prime \; =\; 2,25\; hk\; -\; 1\; \prime \; +\; 1\; \{\backslash \; displaystyle\; h\; \text{'}\_\; \{k\}\; =\; 2.25h\text{'}\; \_\; \{k-1\}\; +1\}$, $h\; 1\; \prime \; =\; 1\; \{\backslash \; displaystyle\; h\; \text{'}\_\; \{1\}\; =\; 1\; \}$, можно рекомендовать для практического применения.

Выполняется следующее свойство: после h 2 -сортировки любого h 1 -сортированного массива массив остается h 1 - отсортировано. Каждый h 1 -сортированный и h 2 -сортированный массив также (a 1h1+a2div class="ht") -сортированный для любых неотрицательных целых чисел a 1 и a 2. Таким образом, наихудшая сложность Shellsort связана с проблемой Фробениуса : для заданных целых чисел h 1,..., h n с gcd = 1, число Фробениуса g (h 1,..., h n) является наибольшим целым числом, которое не может быть представлено как 1h1+... + a nhnс неотрицательное целое число a 1,..., a n. Используя известные формулы для чисел Фробениуса, мы можем определить наихудшую сложность Shellsort для нескольких классов разрывных последовательностей. Проверенные результаты показаны в таблице выше.

Что касается среднего количества операций, ни один из доказанных результатов не касается практической последовательности пропусков. Для пробелов, равных степени двойки, Эспелид вычислил это среднее как $0,5349\; NN\; -\; 0,4387\; N\; -\; 0,097\; N\; +\; O\; (1)\; \{\backslash \; displaystyle\; 0,5349N\; \{\backslash \; sqrt\; \{N\}\}\; -\; 0,4387N-0,097\; \{\backslash \; sqrt\; \{\; N\}\}\; +\; O\; (1)\}$.Кнут определил, что средняя сложность сортировки N-элементного массива с двумя пробелами (h, 1) равна $2\; N\; 2\; h\; +\; \pi \; N\; 3\; h\; \{\; \backslash \; displaystyle\; \{\backslash \; frac\; \{2N\; ^\; \{2\}\}\; \{h\}\}\; +\; \{\backslash \; sqrt\; \{\backslash \; pi\; N\; ^\; \{3\}\; h\}\}\}$. Отсюда следует, что двухпроходная сортировка Shellsort с h = Θ (N) делает в среднем O (N) сравнений / инверсий / время работы. Яо обнаружил среднюю сложность трехпроходной сортировки по шеллу. Его результат был уточнен Янсоном и Кнутом: среднее количество сравнений / инверсий / времени выполнения, сделанных во время сортировки Shellsort с тремя пробелами (ch, cg, 1), где h и g взаимно просты, составляет $N\; 2\; 4\; ch\; +\; O\; (N)\; \{\backslash \; displaystyle\; \{\backslash \; frac\; \{N\; ^\; \{2\}\}\; \{4ch\}\}\; +\; O\; (N)\}$в первом проходе, $1\; 8\; г\; \pi \; ch\; (h\; -\; 1)\; N\; 3/2\; +\; O\; (час\; N)\; \{\backslash \; displaystyle\; \{\backslash \; frac\; \{1\}\; \{8g\}\}\; \{\backslash \; sqrt\; \{\backslash \; frac\; \{\backslash \; pi\}\; \{ch\}\}\}\; (h-1)\; N\; ^\; \{3/2\; \}\; +\; O\; (hN)\}$во втором проходе и $\psi \; (h,\; g)\; N\; +\; 1\; 8\; \pi \; c\; (c\; -\; 1)\; N\; 3/2\; +\; O\; ((c\; -\; 1)\; gh\; 1/2\; N)\; +\; O\; (c\; 2\; g\; 3\; h\; 2)\; \{\backslash \; displaystyle\; \backslash \; psi\; (h,\; g)\; N\; +\; \{\backslash \; frac\; \{1\}\; \{8\}\}\; \{\backslash \; sqrt\; \{\backslash \; frac\; \{\backslash \; pi\}\; \{c\}\; \}\}\; (c-1)\; N\; ^\; \{3/2\}\; +\; O\; \backslash \; left\; ((c-1)\; gh\; ^\; \{1/2\}\; N\; \backslash \; right)\; +\; O\; \backslash \; left\; (c\; ^\; \{2\}\; g\; ^\; \{3\}\; h\; ^\; \{2\}\; \backslash \; right)\}$в третьем проходе. ψ (h, g) в последней формуле - сложная функция, асимптотически равная $\pi \; h\; 128\; g\; +\; O\; (g\; -\; 1/2\; h\; 1/2)\; +\; O\; (gh\; -\; 1/2)\; \{\backslash \; displaystyle\; \{\; \backslash \; sqrt\; \{\backslash \; frac\; \{\backslash \; pi\; h\}\; \{128\}\}\}\; g\; +\; O\; \backslash \; left\; (g\; ^\; \{-\; 1/2\}\; h\; ^\; \{1/2\}\; \backslash \; right)\; +\; O\; \backslash \; left\; (gh\; ^\; \{-\; 1\; /\; 2\}\; \backslash \; right)\}$. В частности, когда h = Θ (N) и g = Θ (N), среднее время сортировки составляет O (N).

На основании экспериментов предполагается, что Shellsort с последовательностью промежутков Хиббарда выполняется в среднем за O (N) времени, а для последовательности Гоннета и Баезы-Йейтса требуется в среднем 0,41NlnN ( ln lnN + 1/6) элемент перемещается. Приближение среднего числа операций, ранее выдвигавшихся для других последовательностей, не дает результата, если отсортированные массивы содержат миллионы элементов.

На приведенном ниже графике показано среднее количество сравнений элементов в различных вариантах Shellsort, разделенное на теоретическую нижнюю границу, т.е. log 2 N !, где последовательность 1, 4, 10, 23, 57, 132, 301, 701 был расширен по формуле $hk\; =\; \lfloor \; 2.25\; hk\; -\; 1\; \rfloor \; \{\backslash \; displaystyle\; h\_\; \{k\}\; =\; \backslash \; lfloor\; 2.25h\_\; \{k-1\}\; \backslash \; rfloor\}$.

Применяя теорию сложности Колмогорова, Цзян, Ли и Витаньи доказали следующую нижнюю границу для порядка среднего числа операций / времени выполнения в p-проход Shellsort: Ω (pN), когда p≤log 2 N и Ω (pN), когда p>log 2 N. Следовательно, Shellsort имеет перспективы работать за среднее время, которое асимптотически растет, как NlogN, только при использовании последовательностей пропусков, количество пропусков которых растет пропорционально логарифму размера массива. Однако неизвестно, сможет ли Shellsort достичь этого асимптотического порядка средней сложности, который является оптимальным для сортировок сравнения. Нижняя граница была улучшена на Витани для каждого количества проходов $p\; \{\backslash \; displaystyle\; p\}$до $Ом\; (N\; \sum \; k\; =\; 1\; phk\; -\; 1\; /\; hk)\; \{\backslash \; displaystyle\; \backslash \; Omega\; (N\; \backslash \; sum\; \_\; \{k\; =\; 1\}\; ^\; \{p\}\; h\_\; \{k-1\}\; /\; h\_\; \{k\})\}$где $h\; 0\; =\; N\; \{\backslash \; displaystyle\; h\_\; \{0\}\; =\; N\}$. Этот результат подразумевает, например, нижнюю границу Цзян-Ли-Витаньи для всех $p\; \{\backslash \; displaystyle\; p\}$-проходных последовательностей приращений и улучшает эту нижнюю границу для конкретных последовательностей приращений. Фактически все границы (нижняя и верхняя), известные в настоящее время для среднего случая, точно совпадают с этой нижней границей. Например, это дает новый результат: верхняя граница Janson - Knuth совпадает с результирующей нижней границей для используемой последовательности приращения, показывая, что трехпроходная сортировка Shellsort для этой последовательности приращения использует $\Theta \; (N\; 23/15)\; \{\backslash \; displaystyle\; \backslash \; Theta\; (N\; ^\; \{23/15\})\}$сравнения / инверсии / время выполнения. Формула позволяет нам искать последовательности приращения, которые дают неизвестные нижние границы; например, последовательность приращений для четырех проходов, нижняя граница которой больше $\Omega \; (pn\; 1\; +\; 1\; /\; p)\; =\; \Omega \; (n\; 5/4)\; \{\backslash \; displaystyle\; \backslash \; Omega\; (pn\; ^\; \{1\; +\; 1\; /\; p\})\; =\; \backslash \; Omega\; (n\; ^\; \{5/4\})\}$для последовательности приращения $h\; 1\; =\; n\; 11/16,\; h\; 2\; =\; n\; 7/16,\; h\; 3\; =\; n\; 3/16,\; час\; 4\; =\; 1\; \{\backslash \; displaystyle\; h\_\; \{1\}\; =\; n\; ^\; \{11/16\},\; h\_\; \{2\}\; =\; n\; ^\; \{7/16\},\; h\_\; \{3\}\; =\; n\; ^\; \{3/16\},\; h\_\; \{4\; \}\; =\; 1\}$. Нижняя граница принимает вид $T\; =\; \Omega \; (n\; \cdot \; (n\; 1\; -\; 11/16\; +\; n\; 11/16\; -\; 7/16\; +\; n\; 7/16\; -\; 3/16\; +\; n\; 3/16)\; =\; \Omega \; (n\; 1\; +\; 5/16)\; =\; \Omega \; (n\; 21/16).\; \{\backslash \; Displaystyle\; T\; =\; \backslash \; Omega\; (n\; \backslash \; cdot\; (n\; ^\; \{1-11\; /\; 16\}\; +\; n\; ^\; \{11\; /\; 16-7\; /\; 16\}\; +\; n\; ^\; \{\; 7\; /\; 16-3\; /\; 16\}\; +\; n\; ^\; \{3/16\})\; =\; \backslash \; Omega\; (n\; ^\; \{1\; +\; 5/16\})\; =\; \backslash \; Omega\; (n\; ^\; \{21/16\}).\}$

Худшее Сложность случая любой версии Shellsort имеет более высокий порядок: Plaxton, Poonen и Suel показали, что она растет, по крайней мере, так же быстро, как $\Omega \; (N\; (log\; \; N\; журнал\; \; журнал\; \; N)\; 2)\; \{\backslash \; displaystyle\; \backslash \; Omega\; \backslash \; left\; (N\; \backslash \; left\; (\{\{\backslash \; log\; N\}\; \backslash \; over\; \{\backslash \; log\; \backslash \; log\; N\}\}\; \backslash \; right)\; ^\; \{2\}\; \backslash \; right)\}$.

Shellsort выполняет больше операций и имеет более высокий коэффициент промахов кэша, чем quicksort. Однако, поскольку он может быть реализован с использованием небольшого количества кода и не использует стек вызовов, некоторые реализации функции qsort в стандартной библиотеке C, ориентированной на встроенные системы, используют его вместо быстрой сортировки. Shellsort, например, используется в uClibc l библиотека. По аналогичным причинам в прошлом Shellsort использовался в ядре Linux.

Shellsort также может служить под-алгоритмом интроспективной сортировки для сортировки коротких подмассивов и предотвращения замедления, когда глубина рекурсии превышает заданный предел. Этот принцип используется, например, в компрессоре bzip2.

• Сортировка гребенок

• Knuth, Donald E (1997). «Метод Шелл». Искусство программирования. Том 3: Сортировка и поиск (2-е изд.). Ридинг, Массачусетс: Эддисон-Уэсли. С. 83–95. ISBN 978-0-201-89685-5.
• Анализ Shellsort и связанных алгоритмов, Роберт Седжвик, Четвертый Европейский симпозиум по алгоритмам, Барселона, сентябрь 1996 г.

В Викибуке Реализация алгоритма имеет страницу по теме: Сортировка оболочки

• Анимированные алгоритмы сортировки: сортировка оболочки на Wayback Machine (заархивировано 10 марта 2015 г.) - графическая демонстрация
• Shellsort с пробелами 5, 3, 1 как венгерский народный танец