Editing Cocktail shaker sort (section)

==Complexity==
The complexity of the cocktail shaker sort in [[big O notation]] is <math>O(n^2)</math> for both the worst case and the average case, but it becomes closer to <math>O(n)</math> if the list is mostly ordered before applying the sorting algorithm. For example, if every element is at a position that differs by at most k (k ≥ 1) from the position it is going to end up in, the complexity of cocktail shaker sort becomes <math>O(kn).</math>

The cocktail shaker sort is also briefly discussed in the book ''[[The Art of Computer Programming]]'', along with similar refinements of bubble sort. In conclusion, Knuth states about bubble sort and its improvements:
{{quote|But none of these refinements leads to an algorithm better than straight insertion [that is, [[insertion sort]]]; and we already know that straight insertion isn't suitable for large&nbsp;''N''. [...] In short, the bubble sort seems to have nothing to recommend it, except a catchy name and the fact that it leads to some interesting theoretical problems.|D. E. Knuth<ref name="Knuth"/>
}}