338
правок
Изменения
м
Нет описания правки
<tex>S - ~ </tex> {{---}} размер остатка вместе с буфером. Используя квадратичную или более быструю сортировку, которая требует <tex> O(1) </tex> дополнительной памяти, отсортируем подмассив длиной <tex> 2S </tex>, который находится в конце.
Так как <tex>S < 2 \sqrt{n}</tex>, то сортировка пройдет за <tex>O(n)</tex>.
