Stooge Sort
- Ω( n2.71 )
- Θ( n2.71 )
- O( n2.71 )
- space O( log n )
Stooge Sort is limited to 150 elements: on average it takes Θ( n2.71 ) 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 stooge sort works
Stooge sort is a deliberately inefficient recursive algorithm. It swaps the first and last element if they are out of order, then sorts the first two thirds, the last two thirds, and the first two thirds again.
Read more
It runs in O(n^2.71), slower than bubble sort. It is correct, which is the interesting part: the overlapping thirds guarantee that the largest elements reach the end. The size is limited so the animation stays within a manageable number of steps.
| Best time | Ω( n2.71 ) | poor |
|---|---|---|
| Average time | Θ( n2.71 ) | poor |
| Worst time | O( n2.71 ) | poor |
| Worst space | O( log n ) | 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.