Bogo sort takes generate-and-test literally. It checks whether the array is sorted, shuffles when it is not, then starts over. With n distinct values, only one of the n! permutations is sorted, so each random attempt succeeds with probability 1/n!. The shuffles can miss forever.
Bogo Sort is useful as a counterexample. Practical sorting algorithms preserve progress by shrinking the unsorted region or removing disorder. Bogo Sort discards 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
Expected: Θ(n · n!)
Worst: Unbounded without an attempt cap
n
number of distinct elements in the array
Attempt cap and termination
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. The initial state is checked before the attempt budget starts, and maxAttempts counts the later shuffles. Every allowed shuffle is checked, including the last one. Returning false makes the cap explicit instead of claiming success with an unsorted array.