cocktail sort in C++
Cocktail sort, also known as bidirectional bubble sort, cocktail shaker sort, shaker sort (which can also refer to a variant of selection sort), ripple sort, shuttle sort or happy hour sort, is a variation of bubble sort that is both a stable sorting algorithm and a comparison sort. The algorithm differs from bubble sort in that sorts in both directions each pass through the list.

void cocktail_sort (int A[], int n)
{
    int left = 0, right = n;
    bool finished;
    do
    {
        finished = true;
        --right;
        for (int i = left; i < right; i++)
            if (A[i] > A[i+1]) {
                std::swap(A[i], A[i+1]);
                finished = false;
            }
        if (finished) return;
        finished = true;
        for (int i = right; i > left; i--)
            if (A[i] < A[i-1]) {
                std::swap(A[i], A[i-1]);
                finished = false;
            }
        ++left;
    } while (!finished);
}