Cocktail Shaker Sort

Cocktail shaker sort is bidirectional Bubble Sort. A forward pass swaps adjacent inversions and fixes the largest remaining value at the right boundary. A backward pass then fixes the smallest remaining value at the left boundary. Both boundaries shrink after a round.

The backward pass repairs Bubble Sort’s asymmetry: a small value near the tail can travel many positions toward the front in one round instead of one position per forward pass. Strict comparison keeps equal values from crossing, so the result is stable. Its value is explanatory rather than production performance.

VisualizationVisualizationComplexityComplexity

Visualization

The forward sweep carries the largest live value to the right edge. The backward sweep carries the smallest live value to the left edge. A complete sweep with no swap proves that no adjacent inversion remains, so the array is sorted.

Complexity

n

number of elements in the array

TimeSpace

• Best
• Average
• Worst

Boundary and implementation

Early exit depends on stopping after a swap-free round. Removing that flag schedules every shrinking pass even when the input is already ordered. Bidirectional motion improves some displaced-value patterns, but Insertion Sort is usually the better simple algorithm for small or nearly sorted inputs.

C# implementation

public static void CocktailShakerSort(int[] values)
{
    var left = 0;
    var right = values.Length - 1;
    var swapped = true;
 
    while (swapped && left < right)
    {
        swapped = false;
        for (var i = left; i < right; i++)
            if (values[i] > values[i + 1])
            {
                (values[i], values[i + 1]) = (values[i + 1], values[i]);
                swapped = true;
            }
 
        right--;
        if (!swapped) break;
 
        swapped = false;
        for (var i = right; i > left; i--)
            if (values[i - 1] > values[i])
            {
                (values[i - 1], values[i]) = (values[i], values[i - 1]);
                swapped = true;
            }
 
        left++;
    }
}

Strict comparison preserves equal-key order; changing > to >= would make the implementation unstable.

Questions

What does each direction settle?

The forward pass fixes the largest live value at the right boundary; the backward pass fixes the smallest live value at the left boundary.

Why is cocktail shaker sort still a teaching algorithm?

Two-way movement repairs Bubble Sort’s one-direction weakness but not its quadratic comparison count. General-purpose O(n log n) sorts dominate once inputs are not tiny.

References

• Donald Knuth, The Art of Computer Programming, Volume 3 — the primary sorting text discussing oscillating/shaker refinements to exchange sorting.
• NIST Dictionary of Algorithms and Data Structures: bidirectional bubble sort — authoritative definition of the alternating-direction Bubble Sort variant.