Bogosort

Bogosort is a particularly ineffective sorting algorithm. Used to sort a deck of cards, it would consist of repeatedly throwing the deck in the air, picking the cards up at random, and testing whether the cards are in sorted order. It is named after the humorous term quantum bogodynamics and ultimately, the word bogus. Other names are stupid sort, bozo sort, blort sort, monkey sort, random sort, stochastic sort, and drunk man sort.

Bogosort is not a stable sort.

Pseudocode

function bogosort(array) while not is_sorted(array) array := random_permutation(array)

Running time and termination

This sorting algorithm is probabilistic in nature. If all elements to be sorted are distinct, the expected complexity is O(n × n!). The exact expected running time depends on how many different element values occur, and how often each of them occurs, but for non-trivial cases the expected running time is exponential or super-exponential in n. It terminates for the same reason that the infinite monkey theorem holds; there is some probability of getting the right permutation, so given an unbounded number of tries it must eventually find it.

It should be noted that with real-world pseudo-random number algorithms, which have a finite number of states and are not in any case actually random, the algorithm may never terminate for certain inputs.

Caveat

If you use the same random number algorithm and the same starting seed to sort the array as was used to randomize the array, you can be surprised by successfully sorting in one iteration. This is caused by the failure of a computer to produce random numbers. Do not expect such a quick resolution with true random numbers or another seed.

Bozo sort

A horrible and most inefficient sorting algorithm that sorts a list by picking two random items in the list, swapping them, and checking if the list is now in order. For an explanation of why bozo sort will almost surely succeed, see Infinite Monkey Theorem.

Quantum Bogosort

A (joke) variant of bogosort, quantum bogosort is distinct in having a time complexity of O(n). It does this by using true quantum randomness to randomly permute the list. The list is then tested for sortedness (requiring n-1 comparisons); if it is not sorted, the universe is destroyed. By the many-worlds interpretation of quantum physics, the quantum randomization spawns an infinite array of universes, a subset of which contains the correctly sorted list. By destroying the universes in which this isn't the case, only the successful reordering is observed — effectively sorting the list on the first try.

External links

Jargon File entry for bogo-sort, "the archetypal perversely awful algorithm"
http://c2.com/cgi/wiki?BogoSort