About Cocktail Shaker Sort
Cocktail Shaker Sort (also called bidirectional Bubble Sort) improves on Bubble Sort by traversing the array in both directions on each iteration. A forward pass bubbles the largest remaining element to the end; a backward pass bubbles the smallest remaining element to the front. This two-way motion fixes 'turtles' — small values near the end that Bubble Sort moves only one step per pass — so the sorted region grows from both ends. It remains a stable, in-place O(n²) algorithm, but often finishes in fewer passes than plain Bubble Sort.
Complexity Analysis
- Time Complexity
- O(n²)
- Space Complexity
- O(1)
- Difficulty
- beginner
Key Concepts
Bidirectional Passes
Each iteration makes a forward pass (bubbling the largest element to the end) and a backward pass (bubbling the smallest to the front). The sorted region therefore grows inward from both ends.
Fixing Turtles
A small value near the end of the array — a 'turtle' — moves only one position per pass in plain Bubble Sort. The backward pass moves it many positions at once, which is where Cocktail Sort earns its keep.
Early Termination
If a full pass completes with no swaps, the array is already sorted and the algorithm stops immediately, giving O(n) best-case time on sorted input.
Common Pitfalls
Same asymptotic class as Bubble Sort
Cocktail Sort is a constant-factor improvement, not an asymptotic one: it is still O(n²) in the average and worst cases.
Shrinking both bounds
After the forward pass the end shrinks; after the backward pass the start grows. Forgetting to update both bounds leads to redundant comparisons or missed elements.