Cocktail Shaker Sort

What is cocktail shaker sort?

Cocktail shaker sort is bubble sort that goes both ways. One sweep goes left to right and pushes the biggest value to the end. The next sweep goes right to left and pulls the smallest value to the front. Back and forth, like shaking a cocktail.

It is also called bidirectional bubble sort or shaker sort. It fixes one weak spot of bubble sort: a small value near the end. In bubble sort that value moves left only one step per pass. Here, every backward sweep carries it all the way.

How it works, step by step

Press play above. Blue bars are being compared, orange bars are being swapped. Watch the sorted green part grow from both ends at once.

1. Forward sweep: compare each pair of neighbors from left to right and swap when the left one is bigger. The biggest value ends up at the right end.
2. Backward sweep: compare each pair from right to left and swap when the left one is bigger. The smallest value ends up at the left end.
3. Both ends are now fixed, so the next round works on a shorter middle part.
4. Repeat until the middle part is empty.

In the code, round p sweeps forward over range(p, n - 1 - p) and backward over range(n - 2 - p, p, -1). Each round shrinks the range by one on each side.

Time and space complexity

Each round sweeps the middle part twice, and there are about n/2 rounds. That adds up to about n²/2 comparisons, the same order as bubble sort: O(n²) on average and in the worst case.

The worst case is a reversed list. Every comparison finds a pair out of order, so every comparison is also a swap. Try the “reversed” preset and watch the swap count climb.

The best case depends on one detail. If you keep a swapped flag and stop when a whole sweep makes no swaps, a sorted list takes one sweep: O(n). The runs recorded for this demo do exactly that. The short version in the code panel leaves the flag out to stay readable, so as written it always does all n/2 rounds and stays O(n²) even on sorted input. Adding the flag is two lines, the same as in bubble sort.

Space is O(1). It swaps values in place.

Is it faster than bubble sort?

A little, on some inputs. Bubble sort struggles with “turtles”, small values near the end, because they creep left one step per pass. Cocktail shaker sort moves a turtle all the way in one backward sweep.

For example, [2, 3, 4, 5, 1] takes bubble sort four passes, because the 1 moves one step per pass. Cocktail shaker sort fixes it in one round: the backward sweep carries the 1 straight to the front.

On a random list the gain is small, often around a third fewer comparisons, and the Big-O is the same.

Common mistakes

• Not shrinking the range from both sides. After each round, one more value is fixed at each end.
• Getting the backward loop bounds wrong. It compares a[i - 1] and a[i], so i must stop at p + 1, not p.
• Forgetting the early exit and then claiming O(n) on sorted input.

When to use it

Mostly for learning. It shows how a small change in direction fixes a specific weakness, which is a useful way to think about any algorithm.

For real lists, insertion sort is simpler and usually faster among the O(n²) sorts, and your language’s built-in sort beats them all on anything big. If you like the idea of fixing turtles, look at comb sort, which attacks them with large gaps instead.

Questions

Is cocktail shaker sort stable?

Yes. Like bubble sort, it only swaps neighbors when the left one is strictly bigger, so equal values never pass each other.

Why is it called cocktail shaker sort?

The sweeps go back and forth across the list, like shaking a cocktail shaker.

What is a turtle in sorting?

A small value near the end of the list. Bubble sort moves it left only one step per pass, which makes it slow.