Bogo Sort
Joke algorithm: keep reshuffling until the array is sorted by sheer luck.
- Comparisons 0
- Swaps 0
- sorted indices 0
- compare
- swap
- sorted
Pseudocode
1 function bogoSort(a)
2 while not isSorted(a)
3 shuffle(a)
4 return a
5
6 function isSorted(a)
7 for i from 1 to n - 1
8 if a[i - 1] > a[i] return false
9 return true
10
11 function shuffle(a)
12 for i from n - 1 downto 1
13 j = random(0, i)
14 swap a[i], a[j]
Step log
How it works, runtime and memory
Bogo Sort (also known as Stupid Sort, Slow Sort or Permutation Sort) is a joke sorting algorithm that turns every textbook statement on efficiency on its head. The idea is dead simple: check whether the array is sorted; if not, reshuffle it completely (typically via Fisher-Yates) and check again. Repeat until pure chance produces a sorted permutation. In the best case the array is already sorted on entry (one isSorted check, O(n)). On average roughly n!/(n − 1) ≈ n!/n shuffles are required, plus one ordering check per shuffle, giving an expected runtime of O(n · n!). The worst case is unbounded: in theory the algorithm need not terminate at all, because the same wrong permutation can come up arbitrarily often. Memory is O(1); not stable, since the shuffle destroys any order among equal keys. This visualisation caps at 80 shuffle rounds so the player does not run forever.
Complexity
- Best case
O(n) - Average case
O(n · n!) - Worst case
O(∞) - Extra space
O(1)
When to use it
A teaching example for expected value, permutations and probability theory and a punchline in algorithms lectures. Never used in production: even ten elements need around 3.6 million shuffles on average, twenty elements need more than two quintillion. Anyone shipping Bogo Sort has a bug, lost a bet, or both.