According to Wikipedia, the Cocktail sort is also known as a bidirectional bubble sort, cocktail shaker sort, ripple sort and many of other names. This sorting algorithm is a variation of the bubble sort that is both a stable sorting algorithm and comparison sort. This algorithm differs from the Bubble sort in that it sorts in both directions each pass through the list.

The Cocktail sort is only a slight variation of the Bubble sort. This sorting algorithm achieves slightly better performance than a standard Bubble sort implementation as it instead of repeatedly passing through the list from top to bottom, the Cocktail sort passes from the bottom to top and then from top to bottom. An example of this can be proved by a list containing five integers ( [2, 3, 4, 5, 1] ) as the Bubble sort will require four passes of this list to sort it where as the Cocktail sort will require one.

The complexity of this sorting algorithm is O(n²). The worst case and average case is also O(n²). However, this algorithms becomes closer to O(n) if the list is mostly sorted. If every element within the list is at a position that differs at most k(k = 1) from the position it is going to end up, the complexity of the Cocktail sort becomes O(k * n).

To quote Donald E. Knuth from The Art of Computer Programming:

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

Let’s take a look at the pseudo code for this sorting algorithm:

procedure CocktailSort( A )
    do
        swapped = false
        for i ? 0 to length( A ) - 1 do
            if A[i] > A[i + 1] then
                swap A[i] ? A[i + 1]
                swapped = true
        end for

        if swapped = false then
            break do-while loop

        swapped = false;
        for i ? length( A ) to 0 do
            if A[i] > A[i + 1] then
                swap A[i] ? A[i + 1]
                swapped = true
        end for
    while swapped

As you can see, this sorting algorithm’s pseudo code is very similar to the Bubble Sort’s. An actual implementation of this sorting algorithm is available below which the standard template library container named Vector.

template<typename T>
void CocktailSort(std::vector<T> *A)
{
	bool swapped = false;
	std::vector<T>::size_type length = A->size();
	do
	{
		swapped = false;
		for( std::vector<T>::size_type i = 0; i < length - 1; ++i )
		{
			if( A->at(i) > A->at(i + 1) )
			{
				std::swap(A->at(i), A->at(i + 1));
				swapped = true;
			}
		}

		if( false == swapped )
		{
			break;
		}

		swapped = false;
		std::vector<T>::size_type size = (length - 2);
		for( std::vector<T>::size_type i = size; i >= 0 && i <= size; --i )
		{
			if( A->at(i) > A->at(i + 1) )
			{
				std::swap(A->at(i), A->at(i + 1));
				swapped = true;
			}
		}
	}
	while( swapped );
}