Cocktail Shaker Sort
A bidirectional bubble sort: each round bubbles the largest value up and the smallest value down, so extremes settle from both ends.
- Category
- Sorting
- Time complexity
- O(n²)
- Space complexity
- O(1)
Pseudocode
loop until no swaps forward pass: bubble large right swap out-of-order neighbours backward pass: bubble small left done
Reference implementation
def cocktail(a):
lo, hi = 0, len(a) - 1
while swapped:
# forward then backward pass
for i in range(lo, hi): ...
for i in range(hi, lo, -1): ...