#ifndef COCKTAIL_SORT_H
#define COCKTAIL_SORT_H

#include <algorithm>
    
template <class RandomAccessIterator>
void cocktail_sort(RandomAccessIterator first, RandomAccessIterator last)
{
    bool finished = false;
    RandomAccessIterator it, begin = first, end = last - 1;
    while (!finished) {
        // Forward pass
        bool changed = false;
        for (it = begin; it < end; ++it) {
            if (*it > *(it + 1)) {
                std::swap(*it, *(it + 1));
                changed = true;
            }
        }
        if (changed) {
            --end;
        }
        else {
            finished = true;
        }
        if (!finished) {
            // Reverse pass
            changed = false;
            for (it = end; it > begin; --it) {
                if (*it < *(it - 1)) {
                    std::swap(*it, *(it - 1));
                    changed = true;
                }
            }
            if (changed) {
                ++begin;
            }
            else {
                finished = true;
            }
        }
    }
}

#endif // COCKTAIL_SORT_H