Cocktail Sort Algorithm

Cocktail sort, also called bidirectional bubble sort or shaker sort, is a variation of bubble sort that sorts an array by passing through it in alternating directions, bubbling the largest unsorted element to the top of the range on a forward pass and the smallest unsorted element to the bottom of the range on the following backward pass, shrinking the unsorted range from both ends at once. This bidirectional approach fixes bubble sort's weakness with small values that start near the end of the array, which an ordinary single-direction bubble sort moves only one position per pass. Like bubble sort, it runs in O(n squared) time in the worst and average case, and is used mainly for teaching rather than performance-sensitive applications.