Когда ожидание заменяет сортировку
Такую шутливую идею можно представить как предельно пассивную сортировку: программа проверяет массив и ничего не делает, пока тот не окажется упорядоченным. В отличие от обычной «глупой сортировки» — bogosort, которая перемешивает элементы и проверяет результат снова, — здесь перемешивание якобы должен обеспечить космический луч.
Но проверка сама по себе не меняет порядок. Алгоритму пришлось бы ждать случайного сбоя в памяти компьютера.
Как луч может изменить данные
Космические лучи — частицы высокой энергии из космоса. Столкнувшись с веществом, они иногда порождают каскад других частиц. Если одна из них попадёт в электронную схему, она может изменить сохранённый бит: например, превратить 0 в 1. Такой случайный сбой называют переворотом бита.
Обычно это не аккуратное перемещение одного числа в массиве, а повреждение отдельных данных. Измениться может и само число, и соседняя ячейка памяти, и состояние программы. Чтобы массив случайно стал отсортированным, изменения должны не просто случиться, но и привести к нужному порядку — без побочных ошибок.
Сортировка, у которой нет срока
Для массива из нескольких разных чисел подходящий порядок всего один среди множества возможных перестановок. Случайное воздействие может приблизить данные к нему, но ничто не заставляет следующий сбой сделать их правильными. А если программа заметит, что данные изменились, это ещё не означает, что она сможет продолжить работу корректно.
Поэтому космический луч здесь — не практический метод сортировки, а комическое воплощение надежды на чрезвычайно удачную случайность. Алгоритм может бесконечно ждать результата, который не умеет приближать сам.
