Cocktail Sort
Bubble Sort that alternates direction each pass and sorts both ends at once.
- Comparisons 0
- Swaps 0
- sorted indices 0
- compare
- swap
- sorted
Pseudocode
1 lo = 0; hi = n - 1; swapped = true
2 while swapped
3 swapped = false
4 for j from lo to hi - 1: if a[j] > a[j+1] swap; swapped = true
5 hi -= 1
6 if not swapped: break
7 for j from hi to lo + 1: if a[j-1] > a[j] swap; swapped = true
8 lo += 1
Step log
- 1Start.
How it works, runtime and memory
Cocktail Sort (also known as Shaker Sort or bidirectional Bubble Sort) is a variant of Bubble Sort. Unlike classical Bubble Sort which always traverses left to right, Cocktail Sort alternates direction: a forward pass pushes the largest element to the right end, then a backward pass pulls the smallest element to the left. This handles the so-called turtles, small elements stuck at the end of the array that only advance one position per Bubble pass, much faster. Worst case stays quadratic O(n²) as for Bubble Sort, best case on already sorted data is linear O(n). Memory is constant O(1) and the algorithm is stable.
Complexity
- Best case
- O(n)
- Average case
- O(n2)
- Worst case
- O(n2)
- Extra space
- O(1)
When to use it
Rarely used in practice because Insertion Sort offers similar benefits on nearly sorted data and runs faster. Cocktail Sort is mostly a teaching example showing how a small tweak to Bubble Sort dramatically improves performance on certain inputs.