Bogo Sort

Randomly swap elements in the list until it's sorted. Thought by some to be the single most inefficient sort one can implement, but this turns out not to be the case; see (for example, generating random permutations of the list until it's sorted is O(N!))

Also known as the RandomSort.

"The archetypical perversely awful algorithm".
-- JargonFile -

One implementation can be found here:

See also MultiplyAndSurrender

Of course, because BogoSort is random, given a random number generator without a set pattern, it has an upper bound of O(infinity).

Ironically, a variant of the BogoSort can sort any list in O(1). See QuantumBogoSort.

View edit of May 26, 2011 or FindPage with title or text search