BogoSort

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 http://home.tiac.net/~cri_d/cri/2001/badsort.html (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 - http://catb.org/~esr/jargon/html/B/bogo-sort.html

One implementation can be found here: http://www.lysator.liu.se/~qha/bogosort/

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.