Bogosort

Bogosort

Class	Sorting
Data structure	Array
Worst-case performance	Unbounded (randomized version), ${\displaystyle O(n\times n!)}$ (deterministic version)
Best-case performance	${\displaystyle \Omega (n)}$
Average performance	${\displaystyle \Theta (n\times n!)}$
Worst-case space complexity	${\displaystyle \mathrm {O} (1)}$

In computer science, bogosort (also known as permutation sort and stupid sort) is a sorting algorithm based on the generate and test paradigm. The function successively generates permutations of its input until it finds one that is sorted. It is not considered useful for sorting, but may be used for educational purposes, to contrast it with more efficient algorithms. The algorithm's name is a portmanteau of the words bogus and sort.

Two versions of this algorithm exist: a deterministic version that enumerates all permutations until it hits a sorted one, and a randomized version that randomly permutes its input and checks whether it is sorted. An analogy for the working of the latter version is to sort a deck of cards by throwing the deck into the air, picking the cards up at random, and repeating the process until the deck is sorted. In a worst-case scenario with this version, the random source is of low quality and happens to make the sorted permutation unlikely to occur.