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