Bogo Sort

Warning

Bogo sort is a teaching example, not a practical sorting algorithm.

Bogo sort uniformly shuffles a sequence until it happens to be sorted. For n distinct elements and independent uniform permutations, a shuffle is sorted with probability 1/n!; the expected number of trials is n!. Each shuffle and check costs Θ(n), so a direct implementation has expected Θ(n · n!) time.

There is no finite deterministic worst-case running-time bound because random trials may continue indefinitely. Repeated values increase the number of sorted permutations and change the probability. The algorithm is useful for discussing randomized termination and the difference between expected and worst-case analysis.