Algorithms and Data Structures · Senior · Question 58 of 75
Why is the recursion depth of quicksort a concern, and how is it bounded?
- ✓Correct answer: Bad pivots give depth n; recurse into the smaller side
- 2Deep recursion makes the sort unstable for equal keys
- 3Depth is always log n, so it's never a concern
Explanation
Recursing into the smaller partition and looping over the larger one guarantees O(log n) stack depth even when the time degrades. Introsort also caps depth and switches to heapsort.