Home/Sorting/Bogo sort
Search algorithmsCTRL K

Bogo sort

· shuffle until it happens to be sorted
/sorting/bogo-sort
SHUFFLES
0
random permutations tried
EXPECTED
24
n! shuffles on average
COMPARISONS
0
in the sortedness checks
CHECKS
0
one before each shuffle
SORTED PREFIX
0
values in order before the first fault
first pair out of orderjust shuffledsorted
n = 4 · seed 7 · 78 steps
step 0 / 77
Size4
bogo_sort.ts
1
function bogoSort(array: number[]) {
2
  while (!isSorted(array)) {
3
    shuffle(array);
4
  }
5
}
6
function isSorted(array: number[]) {
7
  for (let i = 1; i < array.length; i++) if (array[i - 1] > array[i]) return false;
8
  return true;
9
}
10
function shuffle(array: number[]) {
11
  for (let i = array.length - 1; i > 0; i--) swap(array, i, Math.floor(Math.random() * (i + 1)));
12
}
CURRENT STEP
line 1

Start: 4 values in random order. Bogo sort shuffles until the array happens to be sorted; with 4 values that takes 24 shuffles on average (n! = 24).

// how it works

Understanding Bogo sort

bogo sort · the joke at the end of every sorting video
01

The idea

Bogo sort checks whether the array is sorted and, if not, shuffles it at random and checks again. Every shuffle is one of the n! permutations, exactly one of which is sorted, so on average it takes n! shuffles: 24 for four values, 3.6 million for ten, more than the age of the universe for twenty.

It is a real algorithm in the sense that it terminates with probability 1, and a useless one in every other sense. Its value is as a baseline: any idea that beats it is progress, and its analysis is a clean exercise in expected running time. The deterministic cousin, which tries every permutation in order, is called permutation sort.

02

The four stages

1
checkwalk the pairs until one is out of order
2
shuffleFisher–Yates, n − 1 random swaps
3
repeatuntil a check passes
4
doneby luck, eventually
03

Complexity

best
O(n)already sorted: one check
average
O(n · n!)n! shuffles of n swaps each
worst
O(∞)unbounded: it may never finish
space
O(1)in place
04

Versus its siblings

EXPECTED SHUFFLES · n!
n = 4
24
n = 6
720
n = 8
40,320
n = 10
3.6M
bubble n = 10 (comparisons)
45
each shuffle costs n swaps and each check up to n − 1 comparisons
05

Pseudocode

BOGOSORT(array)
  while not ISSORTED(array)
    SHUFFLE(array)
ISSORTED(array): every array[i − 1] ≤ array[i]
SHUFFLE(array): for i from n − 1 down to 1, swap array[i] with array[random in 0..i]
06

When to use

Never, for sorting.
As the baseline in a lecture on expected running time, or as the punchline of one.
07

Pitfalls

A biased shuffle (swapping with a random index from the whole array) makes some permutations likelier than others; Fisher–Yates is the correct one.
The page gives up after 400 shuffles: at n = 6 the expected count is 720, so it usually does.
Quantum bogo sort, which destroys every universe where the shuffle failed, is O(n) and not available.
08

History

The name is a play on bogus; the Jargon File lists it under bogo-sort as a synonym for any hopelessly bad algorithm. Hermann Gruber, Markus Holzer and Oliver Ruepp analysed it seriously in 2007 in 'Sorting the slow way', proving the expected n · n! running time and studying even worse variants.

Back to Sorting