Cocktail shaker sort

Cocktail shaker sort

Class	Sorting algorithm
Data structure	Array
Worst-case performance	${\displaystyle O(n^{2})\,}$
Best-case performance	${\displaystyle O(n)\,}$
Average performance	${\displaystyle O(n^{2})\,}$
Worst-case space complexity	${\displaystyle O(1)}$
Optimal	No

Cocktail shaker sort, also known as bidirectional bubble sort, cocktail sort, shaker sort (which can also refer to a variant of selection sort), ripple sort, shuffle sort, or shuttle sort, is an extension of bubble sort. The algorithm extends bubble sort by operating in two directions. While it improves on bubble sort by more quickly moving items to the beginning of the list, it provides only marginal performance improvements.

Like most variants of bubble sort, cocktail shaker sort is used primarily as an educational tool. More efficient algorithms such as quicksort, merge sort, or timsort are used by the sorting libraries built into popular programming languages such as Python and Java.