Redigerer Bogosortering (avsnitt)

==Tidsforbruk og terminering==
Denne sorteringsalgoritmen er tilfeldig i natur. Hvis alle elementene som skal sorteres er forskjellige er antall forventede sammenlikninger ekvivalent til (e-1)* n!, og antall forventede vekslinger (swaps) er i gjennomstitt lik ''(e-1)''× ''n!''.<ref name="Fun07">H. Gruber, M. Holzer and O. Ruepp: ''[http://www.tcs.ifi.lmu.de/~gruberh/data/fun07-final.pdf Sorting the Slow Way: An Analysis of Perversely Awful Randomized Sorting Algorithms] {{Wayback|url=http://www.tcs.ifi.lmu.de/~gruberh/data/fun07-final.pdf |date=20110719055819 }}'', 4th International Conference on Fun with Algorithms, Castiglioncello, Italy, 2007, Lecture Notes in Computer Science 4475, pp. 183-197.</ref> Forventet antall vekslinger øker fortere enn forventet antall sammenlikninger. Dersom elementene ikke er i rekkefølge kan dette oppdages etter bare noen få sammenlikninger uavhengig hvor mange elementer som finnes. Dog er arbeidet som må til for å blande elementene proporsjonal til samlingens størrelse. I verste fall er antall sammenlikninger og vekslinger begge ubegrensede, akkurat som en mynt kan lande på samme side uendelig mange ganger.

Det beste tilfellet er når listen allerede er sortert. Da er antall forventede sammenlikninger ''n-1'', og innen vekslinger gjøres. Ved sortering av lister med to elementer er Bogosort blant de beste sorteringsmetodene. En sammenlikning og algoritmen avslutter eller gjør en veksling og en til sammenlikning.

Den eksakte kjøretiden avhenger av hvormange forskjellige elementer forekommer og hvor ofte hver av dem oppstår. En kan forvente at for ikke trivielle tilfeller er kjøretiden super-eksponentiell i ''n'' da ''n!'' overgår ''a<sup>n</sup>'' for hver konstant ''a''. Algoritmen termineres av samme grunn som «[[setningen om uendelig mange aper]]» holder; det er en viss sannsynlighet for å få riktig [[permutasjon]]. Så gitt ubegrenset antall forsøk må listen til slutt bli sortert. For at dette skal gå må veksleprosessen aldri gjenta samme mønster, noe som vil skje om det brukes en algoritme for tilfeldighet som ikke er perfekt. Alle psudo-tilfeldige algoritmer er utilstrekkelige.