Cocktail Shaker Sort

Category: Classical
Difficulty: Beginner
Time Complexity: O(n²)
Space Complexity: O(1)

Overview

Cocktail Shaker Sort (also called bidirectional Bubble Sort) improves on Bubble Sort by traversing the array in both directions on each iteration. A forward pass bubbles the largest remaining element to the end; a backward pass bubbles the smallest remaining element to the front. This two-way motion fixes ‘turtles’ — small values near the end that Bubble Sort moves only one step per pass — so the sorted region grows from both ends. It remains a stable, in-place O(n²) algorithm, but often finishes in fewer passes than plain Bubble Sort.

Try It

• Web: Open in Eigenvue →
• Python:

  import eigenvue
  eigenvue.show("cocktail-sort")

Default Inputs

{
  "array": [
    5,
    1,
    4,
    2,
    8,
    3
  ]
}

Input Examples

Default

{
  "array": [
    5,
    1,
    4,
    2,
    8,
    3
  ]
}

Already sorted (one pass)

{
  "array": [
    1,
    2,
    3,
    4,
    5
  ]
}

Reverse sorted (worst case)

{
  "array": [
    5,
    4,
    3,
    2,
    1
  ]
}

Turtle near the end

{
  "array": [
    2,
    3,
    4,
    5,
    1
  ]
}

With duplicates

{
  "array": [
    3,
    1,
    3,
    2,
    1
  ]
}

Code

Pseudocode

function cocktailSort(array):
  start = 0
  end = length(array) - 1
  swapped = true
  while swapped:
    swapped = false
    for i = start to end - 1:
      if array[i] > array[i + 1]:
        swap(array[i], array[i + 1])
        swapped = true
    if not swapped:
      break
    end = end - 1
    for i = end - 1 down to start:
      if array[i] > array[i + 1]:
        swap(array[i], array[i + 1])
        swapped = true
    start = start + 1
  return array

Python

def cocktail_sort(array: list[int]) -> list[int]:
    n = len(array)
    start, end = 0, n - 1
    swapped = True
    while swapped:
        swapped = False
        for i in range(start, end):
            if array[i] > array[i + 1]:
                array[i], array[i + 1] = array[i + 1], array[i]
                swapped = True
        if not swapped:
            break
        end -= 1
        for i in range(end - 1, start - 1, -1):
            if array[i] > array[i + 1]:
                array[i], array[i + 1] = array[i + 1], array[i]
                swapped = True
        start += 1
    return array

JavaScript

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

Key Concepts

Bidirectional Passes

Each iteration makes a forward pass (bubbling the largest element to the end) and a backward pass (bubbling the smallest to the front). The sorted region therefore grows inward from both ends.

Fixing Turtles

A small value near the end of the array — a ‘turtle’ — moves only one position per pass in plain Bubble Sort. The backward pass moves it many positions at once, which is where Cocktail Sort earns its keep.

Early Termination

If a full pass completes with no swaps, the array is already sorted and the algorithm stops immediately, giving O(n) best-case time on sorted input.

Common Pitfalls

• Same asymptotic class as Bubble Sort: Cocktail Sort is a constant-factor improvement, not an asymptotic one: it is still O(n²) in the average and worst cases.
• Shrinking both bounds: After the forward pass the end shrinks; after the backward pass the start grows. Forgetting to update both bounds leads to redundant comparisons or missed elements.

Quiz

Q1: What problem does Cocktail Sort solve compared to Bubble Sort?

• A) It becomes O(n log n)
• B) It moves small values near the end (turtles) faster
• C) It uses no extra comparisons
• D) It becomes stable

Show answer

Answer: B) It moves small values near the end (turtles) faster

The backward pass lets a small element near the end travel toward the front quickly, fixing the ‘turtle’ weakness of one-directional Bubble Sort.

Q2: What is Cocktail Sort’s worst-case time complexity?

• A) O(n)
• B) O(n log n)
• C) O(n²)
• D) O(log n)

Show answer

Answer: C) O(n²)

It is a bidirectional Bubble Sort — still O(n²) in the worst case, just with a smaller constant factor.

Q3: Is Cocktail Shaker Sort stable?

• A) Yes
• B) No
• C) Only forward
• D) Only backward

Show answer

Answer: A) Yes

It swaps only on a strict greater-than comparison in both directions, so equal elements never cross — making it stable.

Further Reading

• Cocktail Shaker Sort — Wikipedia (reference)

Related Algorithms

• Bubble Sort
• Insertion Sort
• Selection Sort