Definition
Bogosort is the sorting algorithm that refuses to take life seriously. The idea is simple:
- Check if the array is sorted.
- If not, shuffle it at random.
- Repeat until sorted.
That is literally it—no guarantees, no efficiency, just chaos.
Complexity
On expectation Bogosort runs in O(n! · n) time because there are n! possible permutations and each shuffle costs O(n). In the worst case the algorithm might never terminate.
In the Gallery
- Watch coloured bars shuffle frantically.
- The moment they accidentally land in order the algorithm triumphantly stops.
- Press "Shuffle" to torment the data again.
See games/js/demos.js for an intentionally terrible implementation.