Cocktail Shaker Sort
Bidirectional bubble sort that traverses in both directions.
Randomly shuffles elements until the array happens to be sorted.
Bogo Sort (also known as permutation sort, stupid sort, slow sort, shotgun sort, or monkey sort) is an intentionally inefficient sorting algorithm based on the generate-and-test paradigm. It repeatedly generates random permutations of the input until it stumbles upon one that happens to be sorted. The algorithm is a staple of computer science humor and serves as a vivid illustration of why algorithmic design matters.
The name "Bogo Sort" is derived from the word "bogus," reflecting the algorithm's absurd approach to sorting. The alternative name "monkey sort" alludes to the infinite monkey theorem -- the idea that a monkey hitting typewriter keys at random for an infinite amount of time would eventually type any given text, including the complete works of Shakespeare. Similarly, Bogo Sort will eventually produce a sorted permutation, but the expected time grows so catastrophically with input size that it is useless in practice. The algorithm has appeared in computer science folklore since at least the 1980s and is frequently used in lectures and textbooks as a counterexample to efficient algorithm design.
That is the entire algorithm. There is no intelligent comparison, no divide-and-conquer strategy, no incremental progress. Each shuffle is completely independent of previous attempts -- the algorithm has no memory of what it has already tried and may generate the same permutation multiple times.
The one interesting component of Bogo Sort is the Fisher-Yates shuffle used in the randomization step. This algorithm iterates through the array from the last element to the first, swapping each element with a randomly chosen element from the remaining unshuffled portion. It produces each of the n! permutations with equal probability and runs in O(n) time. Ironically, this shuffle subroutine is itself a well-designed, efficient algorithm -- it is Bogo Sort's only redeeming feature.
| Case | Time | Space |
|---|---|---|
| Best | O(n) | O(1) |
| Average | O(n * n!) | O(1) |
| Worst | O(infinity) | O(1) |
The best case O(n) occurs when the array is already sorted and a single verification pass confirms it. The average case is O(n * n!) because there are n! possible permutations, each equally likely, and only one is sorted. Each attempt requires O(n) to verify. For 10 elements, n! = 3,628,800, meaning over 3.6 million shuffles on average. For 20 elements, n! is approximately 2.4 * 10^18 -- even at a billion shuffles per second, this would take over 77 years. The worst case is unbounded because randomness offers no guarantee of termination.
Several variants of Bogo Sort exist. Bozo Sort modifies a single random pair of elements instead of shuffling the entire array, resulting in similar expected performance. Deterministic Bogo Sort systematically enumerates all permutations rather than generating random ones, guaranteeing termination in O(n * n!) worst-case time but losing the randomized character. Quantum Bogo Sort is a tongue-in-cheek thought experiment suggesting that quantum mechanics could explore all permutations simultaneously and collapse to the sorted one in O(n) time.
Never, for any practical purpose. Bogo Sort exists purely as a humorous example and a teaching tool for understanding algorithmic complexity, expected values, and the importance of structured approaches to problem-solving. It powerfully demonstrates that an algorithm that makes no progress toward its goal with each step can take an astronomically long time to complete, even on trivially small inputs.