Изменения

Как можно заметить структура поля вывода имеет сходство с [[Персистентный дек| двусвязной очередьюдеком]], а именно мы выбираем край к которому ближе наш элемент, затем добавляем с этой стороны наш элемент и двигаем его. Как мы видим в этом примере понадобилось сдвинуть всего 3 элемента. Благодаря тому что для вставки <tex>j</tex>-ого элемента потребуется <tex>j/2</tex> сдвигов в худшем случае вместо <tex>j</tex>, то и итоговая асимптотика в худшем случае составит <tex>N^2 / 4 + N log N</tex>.