Practice question · Multiple choice
Merge sort guarantees O(n log n) and quicksort is usually preferred anyway. What is quicksort buying, and what is it risking?
Hints
- Ask how much extra memory each algorithm needs.
- What input makes quicksort with a naive pivot behave quadratically?
Show the answer
D. A smaller constant and in-place operation, at the risk of O(n²)
Why
Quicksort partitions in place with excellent cache behaviour, where merge sort allocates a second array, a real cost at scale. The price is a quadratic worst case on sorted input with a naive pivot, mitigated by randomised or median-of-three pivots and by falling back to heapsort, which is what introsort does.
Practise Divide-and-Conquer Reasoning
The app has 6 more questions on this lesson, and keeps your place in the course. Computer Science I is free to start.