Изменения

Как можно заметить структура поля вывода имеет сходство с [[wikipedia:ru:Двусвязная очередь Персистентный дек| двусвязной очередью]], а именно мы выбираем край к которому ближе наш элемент, затем добавляем с этой стороны наш элемент и двигаем его. Как мы видим в этом примере понадобилось сдвинуть всего 3 элемента. Время выполнения алгоритма сократилось в четыре раза, благодаря тому что теперь мы вместо перемещения в среднем для вставки <tex>j</tex>-ого элемента потребуется <tex>Nj/2</tex> мы перемещаем сдвигов в худшем случае вместо <tex>N/4j</tex> элементов : , то и итоговая асимптотика в худшем случае составит <tex>N \cdot (N^2 /84 +\N log N) = N^2/8</tex>.