Bogo Sort
Joke algorithm, also called bogosort or stupid sort: 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
- 1Start.
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.
Frequently asked questions
What is Bogo Sort?
Bogo Sort, also called bogosort, stupid sort or permutation sort, shuffles the array at random and then checks whether it is sorted. If it is not, it shuffles again. It is the textbook example of a deliberately inefficient sorting algorithm.
Is Bogo Sort a joke?
Yes, as a practical algorithm it is meant as a joke and never used. In teaching it shows how fast the number of orderings grows: twelve elements can be arranged in 479,001,600 ways, and on average Bogo Sort tries that many orderings before it hits the sorted one.
What is the best case of Bogo Sort?
In the best case the array is already sorted. One check with n − 1 comparisons is enough, and Bogo Sort finishes in O(n) without a single shuffle.
How long does Bogo Sort take on average and in the worst case?
With n distinct values every ordering is equally likely, so on average n! shuffles are needed, each followed by a check of up to n − 1 comparisons. That gives an expected runtime of O(n · n!). There is no upper bound: the same wrong ordering can come back any number of times, and in the worst case the algorithm never finishes.