Home/Sorting/Cocktail shaker
Search algorithmsCTRL K

Cocktail shaker

· bubble sort in both directions
/sorting/cocktail-shaker-sort
COMPARISONS
0
so far
SWAPS
0
one per inversion fixed
ROUND
0
one sweep each way
IN PLACE
0/ 24
final positions so far
UNSORTED
24
still in the window
comparingswappedin place
n = 24 · seed 7 · 243 steps
step 0 / 242
Size24
cocktail_sort.ts
1
function cocktailSort(array: number[]) {
2
  let low = 0, high = array.length - 1;
3
  while (low < high) {
4
    for (let j = low; j < high; j++) {
5
      if (array[j] > array[j + 1]) swap(array, j, j + 1);
6
    }
7
    high--;
8
    for (let j = high; j > low; j--) {
9
      if (array[j - 1] > array[j]) swap(array, j - 1, j);
10
    }
11
    low++;
12
  }
13
}
CURRENT STEP
line 1

Start: 24 values. Each round sweeps right to carry the largest up, then left to carry the smallest down.

// how it works

Understanding Cocktail shaker

cocktail shaker · the largest goes up, then the smallest comes down
01

The idea

Cocktail shaker sort is bubble sort that changes direction after every pass: a sweep to the right carries the largest unsorted value to its final place, then a sweep to the left carries the smallest one to its place. The unsorted window shrinks from both ends.

The point is the turtle: in plain bubble sort a small value near the end moves left only one position per pass, so it can cost as many passes as there are elements. Sweeping back picks it up in one go. The worst case stays quadratic, but on typical input it roughly halves the number of passes.

02

The four stages

1
sweep rightswap neighbours out of order
2
settle the endthe largest is final
3
sweep leftthe same, backwards
4
settle the startthe smallest is final
03

Complexity

best
O(n)already sorted: one round, no swap
average
O(n²)about half the passes of bubble sort
worst
O(n²)reversed input
space
O(1)in place
04

Versus its siblings

COMPARISONS AT N = 1 000 · RANDOM INPUT
bubble
499,500
cocktail
470,000
insertion
250,000
quick
13,900
merge
8,700
same random input for every algorithm
05

Pseudocode

COCKTAILSORT(array)
  low ← 0; high ← n − 1
  while low < high
    sweep j from low to high − 1: swap array[j], array[j + 1] if out of order; high ← high − 1
    sweep j from high down to low + 1: swap array[j − 1], array[j] if out of order; low ← low + 1
06

When to use

Teaching the turtle problem: the one input where it clearly beats bubble sort.
Nearly sorted data with a few small values at the end.
07

Pitfalls

Still O(n²) comparisons; it saves passes, not comparisons.
Forgetting to shrink both ends repeats work already settled.
Insertion sort beats it on every input for the same code size.
08

History

Also called bidirectional bubble sort, shaker sort or ripple sort, it appears in Knuth's 1973 volume on sorting as a cure for the turtle problem, with the remark that it still does not beat straight insertion. The cocktail name comes from the back-and-forth motion of shaking a drink.

Back to Sorting