Cocktail shaker sort
Cocktail shaker sort is bubble sort with a second sweep added: after a forward pass carries the largest remaining value to the end, a backward pass immediately carries the smallest remaining value to the front, before the boundaries close in from both ends and the two passes repeat.
When it is the right choice
It is a genuine improvement on bubble sort only for a specific input shape: a few small values sitting near the end of an otherwise sorted array, where plain bubble sort needs one pass per position to walk each of them to the front while a single backward sweep here carries them all in one pass. On most other inputs the extra bookkeeping per pass makes it no faster than bubble sort in practice, and both remain far slower than insertion sort or any O(n log n) sort.
How it works
- Sweep forward from the low boundary to the high boundary, swapping each adjacent out-of-order pair, exactly like bubble sort.
- Move the high boundary in by one, since the largest remaining value is now in place.
- Sweep backward from the new high boundary to the low boundary, swapping each adjacent out-of-order pair.
- Move the low boundary in by one, since the smallest remaining value is now in place.
- Repeat both sweeps, shrinking the range from both ends, until a sweep in either direction makes no swaps.
Worth noticing
- The backward sweep is the entire point: a small value one position from the end reaches the front in that single sweep, where plain bubble sort would need almost n passes to walk it there one step at a time.
- It still performs the same order of comparisons and swaps as bubble sort in the worst case — the alternating direction fixes one specific weakness, not the overall O(n²) bound.
- It is stable, for the same reason bubble sort is: two equal values are never swapped past each other, since a swap only happens when one is strictly greater than the other.
Cost
- Best
- O(n)
- Average
- O(n²)
- Worst
- O(n²)
- Extra space
- O(1)
- Stable
- Yes