Bogo Sort
- Ω( n )
- Θ( n · n! )
- unbounded
- space O( 1 )
Array
Comparator strip
Index down, time to the right
Bogo Sort is limited to 7 elements: on average it takes Θ( n · n! ) steps.
- Comparisons count only element-against-element checks; loop and index checks are never counted.
- Reads and writes include reads and writes to helper buffers (merge, counting, radix, bucket and tim sort).
- A swap counts once, as a swap. It is never also counted as a read or a write.
- Real time is the average time of the counted sort on this device over repeated runs, measured once before playback and independent of animation speed. Visual time is the time spent animating, excluding pauses.
How bogo sort works
Bogo sort shuffles the array at random and checks whether it happens to be sorted. If not, it shuffles again. It is the canonical example of a terrible algorithm.
Read more
On average it needs about n! shuffles, so it is limited to 7 elements here. It also stops after 10,000 attempts, which for 7 elements happens about one run in eight, and shows the array as it was left, unsorted.
| Best time | Ω( n ) | good |
|---|---|---|
| Average time | Θ( n · n! ) | poor |
| Worst time | unbounded | poor |
| Worst space | O( 1 ) | good |
Big O notation gives the lower, average and upper bounds of an algorithm. Time complexity bounds the number of operations; space complexity bounds the extra memory it uses.