Проверка, которая может оказаться тяжелее сортировки
Обычная проверка отсортированного списка проста: достаточно пройти по соседним элементам и убедиться, что каждый не больше следующего. Для списка из n элементов это требует примерно n сравнений.
Но здесь проверка устроена иначе: программа делает копию списка и запускает на ней Bogosort — намеренно нелепый алгоритм, который снова и снова перемешивает элементы, пока те случайно не окажутся в нужном порядке. Копия нужна, чтобы беспорядочные перемешивания не испортили исходный список.
Почему ожидание может затянуться
Если все элементы различны, существует n! возможных порядков, и только один из них отсортирован. При случайном перемешивании шанс попасть в него за одну попытку — один из n!; в среднем приходится ждать порядка n! попыток. Это число растёт настолько стремительно, что добавление нескольких элементов способно увеличить ожидание во много раз.
Сам список при этом может быть уже отсортирован — но такой проверке это не помогает: Bogosort всё равно начинает с перемешивания и должен случайно получить правильный порядок заново. Поэтому фраза о том, что проверка не закончится раньше тепловой смерти Вселенной, передаёт абсурдный масштаб ожидания, а не установленный срок. Здесь проверяющая процедура превращает простую задачу в почти безнадёжную.
