Cocktail sort

O(n²)

Cocktail sort (bidirectional bubble sort) alternates direction: one pass bubbles the largest value to the end, the next bubbles the smallest to the front. This clears small values stuck near the end ("turtles") faster than plain bubble sort, though it is still O(n²).

Array
Edit the input and press Play

How it works

  1. Sweep left-to-right, swapping adjacent out-of-order pairs — the largest bubbles to the end.
  2. Sweep right-to-left doing the same — the smallest bubbles to the front.
  3. Shrink the unsorted range from both ends after each pair of passes.
  4. Stop when a full round makes no swaps.

Pseudocode

1cocktailSort(a):                    # O(n²)2  lo ← 0; hi ← n-1; swapped ← true3  while swapped and lo < hi:4    swapped ← false5    for j from lo to hi-1:           # forward pass6      if a[j] > a[j+1]: swap; swapped ← true7    hi ← hi - 18    for j from hi down to lo+1:      # backward pass9      if a[j-1] > a[j]: swap; swapped ← true10    lo ← lo + 1