Cocktail sortCocktail 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.