Summary

Cocktail Sort, also known as Cocktail Shaker Sort or Bidirectional Bubble Sort, is an enhancement of Bubble Sort. Instead of repeatedly passing through the list in one direction, it sorts by passing through the array in alternating directions: first from left to right, then from right to left. This approach helps move items to their correct positions faster, particularly by addressing the problem of "turtles" in Bubble Sort—small elements near the end of the list that are slow to move to the beginning.

How it Works

• 1. Forward Pass: Starting from a boundary start, iterate from left to right. Compare adjacent elements and swap them if they are in the wrong order. This moves the largest unsorted element to the end of the unsorted section.

• After the pass, the last element is sorted. Decrement the end boundary.

• 2. Check for Completion: If no swaps were made during the forward pass, the array is sorted, and the algorithm can terminate.

• 3. Backward Pass: Starting from the new end boundary, iterate from right to left. Compare adjacent elements and swap them if they are in the wrong order. This moves the smallest unsorted element to the beginning of the unsorted section.

• After the pass, the first element is sorted. Increment the start boundary.

• 4. Repeat: Continue these alternating passes, shrinking the start and end boundaries, until the boundaries meet or a pass completes with no swaps.