Two Sigma·Data Scientist·Technical Phone Screen
- Implement merge sort on an integer array, producing a non-decreasing result with O(N log N) time and O(N) auxiliary space. Then walk through a bottom-up iterative version as a follow-up.
- How do you merge two sorted subarrays in O(N) time using a single auxiliary buffer?
- Is merge sort stable? How does that compare to quicksort, and when would you prefer merge sort over quicksort or heapsort?
“I got the recursive version out fine but stumbled when they asked for the iterative bottom-up approach.”