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. This sorting algorithm has worst-case complexity in O(n!), average-case complexity in O((n/2)!) and best-case complexity in O(n). It is also probabilistically not stable.

Bogosort is named after the humourous term quantum bogodynamics.

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 <algorithm>
#include <vector>

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

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