Cocktail sort, also known as
bidirectional bubble sort,
cocktail shaker sort, or
shaker sort, is a
stable sorting algorithm that varies from
bubble sort in that instead of repeatedly passing through the list from top to bottom, it passes alternately from top to bottom and then from bottom to top. Complexity in
Big O notation is O(n²) for a worst case, but becomes closer to O(n) if the list is mostly ordered at the beginning.