---
title: "bogo sort"
type: concept
related: [Bogo Sort, Geometric Random Variable]
source: https://www.jemoka.com/posts/kbhbogo_sort/
confidence: high
status: active
---

Bogo sort!
Consider an algorithm that randomly shuffles the list, check if the list is sorted, and return.
additional information Expected Running Time The expected running time is the number of iterations (\(n!\), in expectation) times the time per iteration (\(n\)).
So the expected running time is \(O\qty(n n!)\).
Worst Case Running Time Infinite (i.e. if randomness is fixed it will take forever).
Some Expectations of Bogo Sort Characteristics Let \(X_{i} = 1\) if \(A\) is sorted after iteration \(i\), \(0\) otherwise. Assuming distinct entries, then \(\mathbb{E}[X_{i}] = \frac{1}{n!}\) (because your list has \(n\) things, so the chance of any given shuffling being sorted is \(\frac{1}{n!}\).)
And the expected number of runs until its sorted is \(n!\) per geometric distribution.
