(algorithm)

**Definition:**
A terribly inefficient *sort* algorithm that repeatedly generates a random *permutation* of the items until the items are in order.

**Generalization** (I am a kind of ...)

*Las Vegas algorithm*.

**See also**
*taco sort*, *bozo sort*, *stooge sort*, *lucky sort*.

*Note:
From the slang "bogus" meaning "bad" as in "I can't believe anybody would be so thoughtless to write/do/say/believe that, and I just can't let it pass without objecting." *

Fastest run time is Θ(n). Average run time is Ω(n × n!). From

**Hermann Gruber, Markus Holzer**, and **Oliver Ruepp**, *Sorting the slow way: An analysis of perversely awful randomized sorting algorithms*, FUN 2007, LNCS 4475, pp. 183-197, 2007. Available at http://www2.tcs.ifi.lmu.de/~gruberh/data/fun07-final.pdf

Note: the permutation subroutine given for Algorithm 1 is *Fisher-Yates shuffle*. Also "Supercalifragilisticexpialidocious" is misspelled on the sixth page, although it is spelled correctly in the footnote.

* Also called "stupid sort".*

Author: PEB

Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 30 September 2013.

HTML page formatted Mon Feb 2 13:10:39 2015.

Cite this as:

Paul E. Black, "bogosort", in
*Dictionary of Algorithms and Data Structures* [online], Vreda Pieterse and Paul E. Black, eds. 30 September 2013. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/bogosort.html