Bogosort

Bogosort

Have you heard of the monkey and the typewriter?

The infinite monkey theorem is a familiar thought experiment, like Schrödinger's cat or the trolley problem. Such experiments explore an imagined situation that is difficult or impossible to realize physically.

A monkey typing randomly for an unlimited time can eventually reproduce Shakespeare's works. Infinitely many monkeys typing indefinitely can produce Hamlet and any other finite text.

This seemingly impossible result follows from probability. In practice, the infinite-time assumption cannot be satisfied. Particular finite-time probability models estimate that even an observable universe filled with typing monkeys could have a probability below $1/10^{183900}$ of producing Hamlet.

The same idea applies to sorting. Randomly permute an array and check its order after each permutation. With independent uniform permutations and indefinitely many attempts, a sorted permutation eventually appears with probability one, but no finite number of attempts guarantees success. Waiting for a useful result can take an impractically long time.