Bogo-Sort

Definitions

1. The canonical maximally inefficient sorting algorithm: shuffle the list at random, check whether it happens to be sorted, and repeat until it is. Average complexity is O(n x n!), which for even modest inputs exceeds the age of the universe. Bogo-sort exists purely as pedagogy and joke, serving as the lower bound against which real algorithms are measured and as a vehicle for teaching expected-case analysis. Its name derives from 'bogus'. Variants proliferate, including bogobogosort, which recursively verifies its own sorted-ness and is slower still, and quantum bogosort, which destroys universes in which the list is unsorted.