Bogosort sorts by repeatedly randomizing a list until the list happens to be in ascending order. Its stopping condition is simple—stop when an ordered scan finds no inversion—but its expected work is impractical: for n distinct items, one successful permutation appears only once in n! equally likely permutations on average.

Bogobogosort is a separate recursive variant, not another spelling for bogosort. It adds nested sorting and retry stages, making its expected behavior even less practical.

How Bogosort Works: Stopping Condition, Pseudocode, and a Tiny Trace

Assume the input contains distinct values and should be sorted in ascending order. Bogosort tests the current order, then randomly shuffles the entire list when the test fails. It stops only after isSorted(A) returns true.

Pseudocode:

1. If isSorted(A) is true, return A.
2. Shuffle A uniformly at random.
3. Repeat steps 1 and 2 until the list is sorted.

For the tiny input [2, 1, 3], the first check fails because 2 precedes 1. A possible shuffle produces [1, 3, 2], which also fails. Another shuffle might produce [3, 2, 1], followed by [1, 2, 3]. The algorithm stops at that point. A random shuffle can repeat an earlier arrangement, so this trace is only one possible path.

Why Does Bogosort’s Expected Runtime Grow Factorially?

With n distinct values, there are n! possible permutations. Under a uniform shuffle, exactly one is sorted, giving each attempt a success probability of 1/n!. The geometric-distribution intuition is therefore straightforward: the expected number of attempts is n!.

That count grows quickly: five items have 120 possible orders, while ten items have 3,628,800. Each attempt also needs an order check, which takes O(n) time. Bogosort consequently has an expected running time commonly expressed as O(n · n!), assuming uniform shuffling and distinct elements.

Its randomized worst case has no finite upper bound. The shuffling process could, in principle, avoid the sorted permutation indefinitely, even though the probability of eventual success is one under standard independent randomization.

How Bogobogosort Differs: A Separate Recursive Variant

Classic bogobogosort uses recursion to make the retry process more deeply nested:

1. Recursively apply bogobogosort to the first n − 1 items.
2. When that prefix is sorted, check the entire list.
3. If the full list is not sorted, shuffle all n items and restart the process.

The one-item case is already sorted and serves as the base case. The defining difference is that an outer attempt can invoke a complete recursive attempt on a shorter prefix before it gets another chance to test the full list. Ordinary bogosort simply shuffles until the whole list is sorted; bogobogosort builds recursive retries into that loop.

Its expected complexity depends on the precise implementation and shuffle model. Informal analyses of the classic variant often describe growth on the order of O((n!)^n!), or otherwise use superfactorial-style estimates. The exact label matters less than the structure: its expected runtime is vastly worse than bogosort’s factorial behavior, and its randomized worst case is likewise unbounded.

Why Are These Algorithms Still Discussed?

Bogosort and bogobogosort are useful cautionary examples rather than practical sorting tools. They make probability concrete, show why factorial search spaces become unmanageable, and demonstrate how a recursive retry can amplify an already poor algorithm. They also help separate expected runtime from worst-case guarantees: a process can be almost certain to finish eventually while still requiring an absurd expected amount of work.