Cocktail sort

A cocktail sort is a variant of a Bubble sort where instead of going through the array forwards each time, the array is iterated first forward and then backward. This implementation also exploit the observation that each pass finds more smallest/largest items, and only iterate over the middle part of the array – the part that is still not completely sorted.

This algorithm is a fair bit more complicated than bubble sort, and is still an $O(N^2)$ algorithm according to Knuth. It is also still almost always slower than Insertion sort, and is not suitable for production use outside very special cases.