Bozo Sort

Warning

Bozo sort is intentionally impractical and appears here only for analysis.

Bozo sort repeatedly chooses two positions uniformly at random, swaps their values, and stops when the sequence is sorted.

Unlike bogo sort, one step does not sample an independent uniform permutation. It performs a random walk over permutations. Its expected hitting time depends on the exact rule—for example, whether choosing the same position twice is allowed—and should not be stated as O(n!) without deriving that model. It has no finite deterministic worst-case termination bound.

The lesson is methodological: a randomized complexity claim needs a defined random process, a cost per step, and the case being reported.