Bogosort

According to the Jargon File, the bogosort is "the archetypal perversely awful algorithm", equivalent to repeatedly throwing a deck of cards in the air, picking them up at random, and then testing whether they are in order. It is named after the humourous term quantum bogodynamics.

Here is the pseudocode of the algorithm:

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

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 should be noted that with real-world pseudo-random number algorithms, which have a finite number of states, the algorithm may never terminate for certain inputs.

The following is an implementation in C++:

include 
include 

template
void bogosort(std::vector& array)
{
   while (! is_sorted(array))
       std::random_shuffle(array.begin(), array.end());
}

template
bool is_sorted(const std::vector& array)
{
   for (typename std::vector::size_type i = 1; i < array.size(); ++i)
       if (array[i] < array[i-1]) return false;
   return true;
}