Как можно заметить структура поля вывода имеет сходство с Двусвязной очередью, а именно мы выбираем край к которому ближе наш элемент, затем добавляем с этой стороны наш элемент и двигаем его. Как мы видим в этом примере понадобилось сдвинуть всего 3 элемента. Время выполнения алгоритма сократилось в четыре раза, благодаря тому что теперь мы вместо перемещения в среднем <tex>N/2</tex> мы перемещаем <tex>N/4</tex> элементов : <tex>O(C \cdot N \cdot (N/8+\log N)) = O(N^2/8)</tex>, следовательно <tex>C=1/8</tex>.
===Вставка в список ===
При этой сортировке мы используем односвязной список вместо упорядоченной части массива. Теперь на не потребуется времени на сдвиг, а понадобиться всего лишь изменить родственные связи. При этом время выполнения сокращается в два раза : <tex>O(C \cdot N \cdot (N/4+2) ) = O( N^2/4)</tex>, следовательно <tex>C=1/4</tex>.
=== Сортировка с вычислением адреса ===
Сортировку с вычисление адреса выгодно использовать когда ключи распределены равномерно и не скапливаются хаотично в отдельных диапазонах значений. Вместо левой отсортированной части массива мы будем использовать <tex> M </tex> односвязных списков, в каждом из которых будут храниться значения из определённого диапазона. С каждым списком работаем как при простых выставках в список. Вероятность того что элемент попадёт в какой-либо список <tex>1/M</tex>, следовательно для каждого элемента происходит примерно <tex>\displaystyle \frac {N} {4 \cdot M} </tex> сравнений, следовательно общее количество сравнений <tex>\displaystyle \frac {N^2} {4 \cdot M} </tex>, а при <tex>M</tex> порядка <tex>N</tex> асимптотическая сложность уменьшается до <tex>O(N)</tex>.
Рассмотрим на примере.
Входные данные : <tex>867, 345, 984, 245, 123, 743, 550, 490, 300</tex>
Будем использовать 4 списка с соответствующими диапазонами значений : <tex>0 - 250, 251 - 500, 501 - 750, 751- 1000</tex>.
{|border="1"
|
|3 элемента
|6 элементов
|9 элементов
|-
|0 - 250
|
|123 245
|123 245
|-
|251 - 500
|345
|345
|300 345 490
|-
|501 - 750
|
|743
|550 743
|-
|751 - 1000
|867 984
|867 984
|867 984
|}
== См. также ==
