Cocktail Sort

Average time complexity - O(n^2)

Best-Case time complexity - O(n)

Worst-Case time complexity - O(n^2)

Worst-case space complexity - O(1)

Cocktail Sort, which is also known as Cocktail Shaker Sort, is a variation of Bubble Sort that iterates through the array both forward and backward. This improves greatly on one of Bubble Sort's weaknesses, namely an array pre-sorted in reverse order. This is because, in Bubble Sort, an element can only move backward one spot per pass.

Cocktail also ignores both the first element and last element sorted in a given pass, because it knows that they are in the correct place. Each half-pass ends on element to the left of the last element sorted in the last pass, and begins one element to the right of the first element sorted in the previous pass.

Let's say we have the following array:

4, 1, 5, 2, 3

Like Bubble Sort, it will iterate through and swap every two element out of order. In this case, the first and **second **are out of order.

1, 4, 5, 2, 3

Now it compares the second and third elements (4 and 5). These are correct, so it moves on to the third and fourth (5 and 2). These are out of order, so it swaps them.

1, 4, 2, 5, 3

Now it compares the fourth and fifth elements (5 and 3), and they are out of order, so it swaps them.

1, 4, 2, 3, 5

Now that one half-pass is complete, it reverses. It compares the fourth and third elements, which are correct. It then compares the third and second elements, which are out of order, so it swaps them.

1, 2, 4, 3, 5

Then it moves on to the second and first, which are correct. The second half of the pass is complete, which makes one full pass.

Now it shall do the process again, but it ignores the first and fifth elements, because it assumes (correctly, always) that they are already in place.

It compares the second and third elements, which are in the right order. Then it compares the third and fourth elements, which are not in order, so it swaps them.

1, 2, 3, 4, 5

It ignores the fourth and fifth. Now it begins going back down from right to left. It will not make any swaps (because the array is sorted), so it will then exit after that half-pass down.