338
правок
Изменения
м
Нет описания правки
Пользуясь буфером обмена, последовательно сольем пары соседних блоков <tex>([0, S - 1]</tex> и <tex>[S, 2 \cdot S - 1],</tex> потом <tex>[S, 2 \cdot S - 1]</tex> и <tex>[2 \cdot S, 3 \cdot S - 1],</tex> и т.д.<tex>)</tex>. В результате мы получим, что первые <tex>len \cdot (cnt - 1)</tex> элементов исходного массива отсортированы.
Количество групп блоков <tex> \sqrt{n} </tex>, и каждое слияние работает за <tex> О O(\sqrt{n}) </tex> , поэтому количество операций на этом шаге <tex> O(n) </tex>.
[[Файл:Merge_O(1)_5.png|center|525px]]
