Cocktail shaker sort is a bi-directional bubble sort. It first “bubbles” up, after which you can be assured that at least the last element of the list is in the right place. Then it bubbles down from next-to-last element of the list to the first, after which you can be assured that the first element of the list is also in the right place. Then it bubbles up again, now starting with the second element, and up to the penultimate element. Then down again, and it keeps going up and down in smaller and smaller sublists until no more swaps take place.

Implement cocktail shaker sort. Determine its time complexity in big-O notation. Does it have advantages over bubble sort?

Note: The submission of this exercise is in markdown and therefore won’t be tested. Use your preferred code editor or Papyrus¹ to test your code.