Implement cocktail shaker sort and analyze
Company: UiPath
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Implement the cocktail shaker sort (bidirectional bubble sort) for an array of integers. Optimize it with early termination and shrinking bounds, and include basic tests. Analyze time and space complexity, stability, and when it outperforms or underperforms standard bubble sort; provide worst-, average-, and best-case comparisons and swaps.
Quick Answer: This question evaluates a candidate's understanding of sorting algorithms and algorithmic optimization, specifically implementation and enhancement of cocktail shaker sort, plus analysis of time and space complexity, stability, and counts of comparisons and swaps.
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.
Constraints
- 0 <= len(arr) <= 10^4
- -10^9 <= arr[i] <= 10^9
- Sort in ascending order
- Must be a stable, in-place sort (cocktail shaker / bidirectional bubble sort)
- Do not mutate the caller's input list
Examples
Input: ([5, 1, 4, 2, 8, 0, 2],)
Expected Output: [0, 1, 2, 2, 4, 5, 8]
Explanation: General unsorted array with a duplicate (two 2s); stable sort keeps equal elements' relative order.
Input: ([],)
Expected Output: []
Explanation: Empty array returns empty — guarded by the n <= 1 early return.
Hints
- Use a boolean `swapped` flag per full cycle; if a forward pass makes no swaps the array is sorted and you can stop early.
- Track the index of the LAST swap on the forward pass and use it as the new `end`; do the same for the backward pass to set a new `start`. This shrinks the window from both sides.
- The backward pass is what makes this beat plain bubble sort: it moves a small element near the tail many positions toward the front in a single pass, instead of one position per full sweep.