This sorting algorithm is probabilistic in nature. If all elements to be sorted are distinct, the expected complexity is O(n!). The algorithm may finish in O(n) if you are extremely lucky, or if all elements are equal. The exact expected running time depends on how many different element values occur, and how often each of them occurs, but for nontrivial cases the expected running time is exponential or superexponential in n.
It should be noted that with realworld pseudorandom 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[i1]) return false; return true; }
Search Encyclopedia

Featured Article
