AlgoViz.
Sorting

Cocktail Shaker Sort

Size:15
Execution Narrative
Step 1 of 159Start
Line 1
Starting Cocktail Shaker Sort on array of 15 elements with bidirectional boundaries [0..14].
Comparisons0
Swaps0
Operations0

Overview & Concept

Cocktail Shaker Sort (Bidirectional Bubble Sort) extends Bubble Sort by traversing the array alternately in both directions. In each pass, it bubbles the maximum unsorted value forward to the right boundary, then reverses direction to sink the minimum unsorted value backward to the left boundary.

How It Works

Bidirectional Traversal: Swaps between forward scan (left-to-right) and backward scan (right-to-left).

Dual Narrowing Boundaries: Maintained via left pointer (starts at 0) and right pointer (starts at n-1) that contract toward the center.

Turtle Mitigation: Solves Bubble Sort's turtle problem where small items near the end take n passes to reach the beginning.

Early Termination: Halts immediately if a complete bidirectional pass finishes with zero swaps.

Step-by-Step Execution

1. Forward PassBubble largest element from left boundary to right boundary; decrement right boundary.
2. Check SwapsIf no swaps occurred in forward pass, array is sorted; break.
3. Backward PassSink smallest element from right boundary down to left boundary; increment left boundary.
4. Repeat until ConvergedContinue until left boundary meets or exceeds right boundary.

Asymptotic Complexity Analysis

MetricBest CaseAverage CaseWorst CaseSpace Complexity
Complexity BoundO(n)O(n²)O(n²)O(1)
ExplanationOptimal input arrangement minimizing operations.Expected time for uniformly distributed randomized inputs.Adversarial degenerate conditions requiring full traversal.Auxiliary memory allocated beyond original input size.

Pseudocode & Invariants

Algorithm Logic
procedure cocktailShakerSort(A):
  start = 0, end = length(A) - 1, swapped = true
  while swapped and start < end:
    swapped = false
    for i = start to end - 1: if A[i] > A[i+1]: swap(A[i], A[i+1]); swapped = true
    end = end - 1
    if not swapped: break
    swapped = false
    for i = end - 1 down to start: if A[i] > A[i+1]: swap(A[i], A[i+1]); swapped = true
    start = start + 1
  return A
Algorithmic Invariants
  • Double Boundary Sortedness: Elements A[0..left-1] and A[right+1..n-1] are permanently sorted at all times.
Correctness Guarantee: Invariants hold true prior to loop entry, are preserved during every iteration, and guarantee correct post-condition upon termination.

Advantages & Disadvantages

Key Advantages

  • •Faster than standard Bubble Sort on arrays where small elements reside near the end.
  • •Strictly stable: maintains the relative order of duplicate items.
  • •In-place sort requiring O(1) auxiliary space.
  • •O(n) best-case time complexity on sorted inputs.

Trade-offs & Limitations

  • •Still O(n²) average and worst-case time complexity.
  • •Significantly slower than O(n log n) algorithms on general unsorted data.

Real-World Applications

Pedagogical Algorithm Demonstrations

Teaching bidirectional traversal and loop invariant shrinking in computer science courses.

Decision Guide: When to Use

Ideal Scenarios

  • ✓When educational clarity or double-ended bubbling is needed.
  • ✓When arrays are nearly sorted with outliers at both boundaries.

Consider Alternatives When

  • ✕In any production sorting scenario on large datasets.

Explore Related Algorithms

Compare trade-offs and complexity across complementary tools in AlgoViz.

Bubble SortComb SortGnome Sort