Stooge Sort Visualization
Stooge Sort recursively sorts the first two thirds, the last two thirds, then the first two thirds again.
How it works
Stooge Sort swaps the first and last elements if needed, then recursively sorts the first two thirds of the range, then the last two thirds, then the first two thirds again. It is correct, and surprisingly hard to see why at first.
It runs in about n^2.71 time, slower than Bubble Sort, which makes it a favourite example of a correct but deliberately inefficient algorithm. It sorts in place apart from the recursion stack.
What to watch for
Watch the same regions get sorted over and over as the recursion overlaps itself.
Complexity
- Best
- n^2.71
- Average
- n^2.71
- Worst
- n^2.71
- Extra space
- log n
- Stable
- No
Race it
Same shuffle, same speed, one winner: Stooge vs Bubble. Or open the studio to try other layouts, sizes and speeds, and make a video of it.
FAQ
Why is it called Stooge Sort?
It is named after the Three Stooges comedy act, for how much redundant work it does.
Why is it capped here?
Its n^2.71 cost explodes quickly, so the visualizer limits it to 128 elements.