Overview
Cocktail Shaker Sort is a bidirectional variant of Bubble Sort. It bubbles the largest element to the end on a left-to-right pass, then the smallest to the front on a right-to-left pass, alternating until sorted.
How Cocktail Shaker Sort works
- Pass left-to-right, swapping adjacent out-of-order pairs so the largest reaches the end.
- Pass right-to-left, doing the same so the smallest reaches the front.
- Shrink the active range from both ends after each pass.
- Stop as soon as a full pass performs no swaps.
When to use it
- Mostly educational — it illustrates how bidirectional passes fix Bubble Sort's 'turtles' (small values near the end).
- Small or nearly-sorted arrays, like other simple quadratic sorts.
Complexity analysis
Like Bubble Sort it is O(n²) on average and worst case, and O(n) on already-sorted input. The two-directional sweep reduces the number of passes in practice but not the asymptotic class. It is in-place and stable.
Frequently asked questions
What advantage does Cocktail Sort have over Bubble Sort?
By sweeping both directions it moves small values stuck near the end ('turtles') forward quickly, so it often needs fewer passes — though both remain O(n²).