Implement **cocktail shaker sort** (also called bidirectional bubble sort) for an array of integers and return the sorted array in ascending order. Cocktail shaker sort improves on standard bubble sort by traversing the array in **both directions** on alternating passes. A forward pass bubbles the largest remaining element toward the end; a backward pass bubbles the smallest remaining element toward the start. This handles 'turtles' (small values near the end that bubble sort moves only one step per full pass) far more efficiently. Optimize your implementation with two techniques: 1. **Early termination** — stop as soon as a full pass makes no swaps (the array is already sorted). 2. **Shrinking bounds** — track the index of the last swap on each pass and tighten the active `[start, end]` window, so already-settled elements at both ends are skipped on subsequent passes. Do not mutate the caller's input list; return a new sorted list. **Example** ``` Input: [5, 1, 4, 2, 8, 0, 2] Output: [0, 1, 2, 2, 4, 5, 8] ``` **Complexity / analysis to keep in mind** - Time: O(n) best case (already sorted, one pass), O(n^2) average and worst case. - Space: O(1) auxiliary (in-place swaps). - Stability: stable — equal elements never jump past one another because swaps only happen on strict `>` comparisons. - vs. bubble sort: cocktail shaker beats bubble sort when small elements ('turtles') sit near the end, since the backward pass moves them many positions at once; it underperforms (does the same asymptotic work, slightly more bookkeeping) on already-near-sorted or randomly-ordered data where the bidirectionality buys little.