Problem: Cocktail Shaker Sort

Let’s fix a weakness of bubble sort that we saw in the chapter.

Recall the two nearly sorted arrays from the chapter. On [5, 1, 2, 3, 4], bubble sort with early termination carries the 5 to the end in one pass, finds nothing to swap on the second pass, and stops after seven comparisons. On [2, 3, 4, 5, 1], which has the same four inversions, it needs four passes and all ten comparisons, because each pass moves the 1 only one slot to the left. A pass sweeps left to right, so a large element can move all the way to the right in one pass, but a small element moves left by only one slot per pass.

Cocktail shaker sort adds a pass in the other direction. Here is [2, 3, 4, 5, 1] after one forward pass, which carries the 5 to the end:

┌───┬───┬───┬───┬───┐
│ 2 │ 3 │ 4 │ 1 │░5░│
└───┴───┴───┴───┴───┘

And after one backward pass, which carries the 1 to the front:

┌───┬───┬───┬───┬───┐
│░1░│ 2 │ 3 │ 4 │░5░│
└───┴───┴───┴───┴───┘

The shaded cells are settled. The unsorted portion shrinks from both ends, one element per pass, so you will want to keep track of where it starts and where it ends.

The signature of the method in Java might look like this:

public static void cocktailShakerSort(int[] arr) {
  // Your implementation goes here
}

Assume there is a swap(arr, i, j) helper that exchanges two elements.

Let’s think of some special or edge cases as well:

• If the array is empty or has one element, there is nothing to compare, and the method should return without touching it.
• If the array is already sorted, the first forward pass swaps nothing, and the sort should stop there without running a backward pass.
• If every element is the same, no comparison ever finds a pair out of order, so this is the sorted case again.
• If the array has two elements, one forward pass either swaps them or finds them in order, and either way the sort is done.