Cocktail Shaker Sort Visual Guide | Draftsbook

Exchange Sorting · Article 32 of 62

Cocktail Shaker Sort

A bidirectional bubble sort: bubbles values back and forth in alternating directions to quickly clear slow-moving small values ("turtles") and large values ("rabbits").

How it works

Cocktail Shaker Sort (also known as Ripple Sort, Shuttle Sort, or Bidirectional Bubble Sort) is a direct extension of Bubble Sort. Plain Bubble Sort only travels left-to-right, meaning a small value at the end of the array (a "turtle") takes a full pass to move left by only one index. Cocktail Shaker Sort resolves this by alternating traversal directions:

Left-to-Right Pass: Compare adjacent elements and swap them if out of order. At the end of the pass, the largest unsorted element is locked in place at the right boundary.
Right-to-Left Pass: Traverse back from the right boundary to the left. Compare adjacent elements and swap if out of order. At the end of this pass, the smallest unsorted element is locked at the left boundary.
Shrink Bounds: Shrink both the left and right boundary indices and repeat the bidirectional passes until a full shake occurs with no swaps.

Complexity

Best time

O(n)

Average time

O(n²)

Worst time

O(n²)

Extra space

O(1)

Stable

Yes

In-place

Yes

By checking for swaps on each bidirectional pass, Cocktail Shaker Sort can terminate in \(O(n)\) time if the array is already sorted, or near-\(O(n)\) if only a few elements are out of position.

Interactive visualization

Pseudocode

procedure cocktailShakerSort(A):
  n ← length(A)
  start ← 0
  end ← n - 1
  swapped ← true
  
  while swapped:
    swapped ← false
    for i from start to end - 1:
      if A[i] > A[i+1]:
        swap A[i], A[i+1]
        swapped ← true
        
    if not swapped:
      break
      
    end ← end - 1
    swapped ← false
    
    for i from end - 1 down to start:
      if A[i] > A[i+1]:
        swap A[i], A[i+1]
        swapped ← true
        
    start ← start + 1

JavaScript implementation

function cocktailShakerSort(arr) {
  let start = 0;
  let end = arr.length - 1;
  let swapped = true;
  
  while (swapped) {
    swapped = false;
    for (let i = start; i < end; i++) {
      if (arr[i] > arr[i + 1]) {
        [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
        swapped = true;
      }
    }
    if (!swapped) break;
    end--;
    
    swapped = false;
    for (let i = end - 1; i >= start; i--) {
      if (arr[i] > arr[i + 1]) {
        [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
        swapped = true;
      }
    }
    start++;
  }
  return arr;
}

Pros and cons

Pros

Stabler and handles turtles far better than standard Bubble Sort.
In-place: requires O(1) extra space.
Highly intuitive to design and implement.

Cons

Worst and average-case performance remain quadratic \(O(n²)\).
Performs many redundant comparisons compared to Insertion Sort.
Rarely used in production settings.

When (not) to use it

Educational purposes: Wonderful for demonstrating double-loop optimization and bidirectional scanning logic.
Nearly sorted arrays: Performs reasonably well if only a few elements are scattered, but Insertion Sort is still preferred.

Up next: Odd-Even Sort — a parallelizable exchange sort that swaps odd-indexed neighbors, then even-indexed neighbors, in alternating sweeps.

Cocktail Shaker Sort: Mechanism, Complexity Analysis & Interactive Visualizer