Bogo sort applies generate-and-test without useful guidance: check whether the array is sorted; if not, shuffle it and try again. For n distinct values only one of the n! permutations is sorted, so a random attempt succeeds with probability 1/n!. A sequence of random shuffles can miss indefinitely.
The algorithm is a counterexample, not a production choice. It makes the value of progress invariants concrete: a real sorting algorithm proves that each step shrinks disorder or fixes a region, while Bogo Sort forgets all previous work after every shuffle.
Visualization
The teaching trace enumerates a deterministic bounded sequence of permutations instead of depending on random luck. It accepts at most five items and stops after at most 120 attempts. Those limits keep the card reproducible and finite; the classical algorithm remains random and has no finite worst-case bound.
Complexity
Bogo Sort complexity
n
number of distinct elements in the array
Expected: Θ(n · n!)
Worst: Unbounded without an attempt cap
Boundary and implementation
The storage result shown above assumes an unbiased Fisher–Yates shuffle that modifies the array directly. An attempt cap makes a program terminate but changes the contract: it may return failure with an unsorted array. The deterministic StepTrace demonstrates the state space; it is not evidence that random Bogo Sort finishes within 120 attempts.
C# bounded demonstration
public static bool TryBogoSort(int[] values, Random random, int maxAttempts){ if (IsSorted(values)) return true; for (var attempt = 0; attempt < maxAttempts; attempt++) { random.Shuffle(values); if (IsSorted(values)) return true; } return false;}private static bool IsSorted(int[] values){ for (var i = 1; i < values.Length; i++) if (values[i - 1] > values[i]) return false; return true;}
Random.Shuffle performs an unbiased shuffle directly on the array in current .NET. maxAttempts counts shuffles: the initial state is checked once, and every shuffle—including the final allowed shuffle—is checked before returning false. Returning false exposes the cap instead of pretending the array was sorted.
Questions
Why is the expected time factorial?
With distinct values, each unbiased shuffle selects one of n! permutations and only one is sorted. The expected number of attempts is proportional to n!; each Fisher–Yates shuffle costs Θ(n), while the order check is O(n) in the worst case, so expected time is Θ(n · n!). The worst case remains unbounded because random shuffles may miss the sorted permutation indefinitely.
What important guarantee does an attempt cap change?
It guarantees termination by allowing failure. The method is no longer a sorting algorithm that always returns a sorted result.