Editing Bogosort (section)

==Running time and termination==
[[File:ExperimentalBogosort.png|thumb|Experimental runtime of bogosort]]
If all elements to be sorted are distinct, the expected number of comparisons performed in the average case by randomized bogosort is [[Asymptotic analysis|asymptotically equivalent to]] {{math|(''e'' − 1)''n''!}}, and the expected number of swaps in the average case equals {{math|(''n'' − 1)''n''!}}.<ref name="Fun07">{{citation
 | last1 = Gruber | first1 = H.
 | last2 = Holzer | first2 = M.
 | last3 = Ruepp | first3 = O.
 | contribution = Sorting the slow way: an analysis of perversely awful randomized sorting algorithms
 | doi = 10.1007/978-3-540-72914-3_17
 | pages = 183–197
 | publisher = Springer-Verlag
 | series = Lecture Notes in Computer Science
 | title = 4th International Conference on Fun with Algorithms, Castiglioncello, Italy, 2007
 | date = 2007
 | url = http://www.hermann-gruber.com/pdf/fun07-final.pdf
 | volume = 4475| isbn = 978-3-540-72913-6
 }}.</ref> The expected number of swaps grows faster than the expected number of comparisons, because if the elements are not in order, this will usually be discovered after only a few comparisons, no matter how many elements there are; but the work of shuffling the collection is proportional to its size. In the worst case, the number of comparisons and swaps are both unbounded, for the same reason that a tossed coin might turn up heads any number of times in a row.

The best case occurs if the list as given is already sorted; in this case the expected number of comparisons is {{math|''n'' − 1}}, and no swaps at all are carried out.<ref name="Fun07"/>

For any collection of fixed size, the expected running time of the algorithm is finite for much the same reason that the [[infinite monkey theorem]] holds: there is some probability of getting the right permutation, so given an unbounded number of tries it will [[almost surely]] eventually be chosen.