Algorithms and Data Structures · Middle · Question 2 of 75
What is the main drawback of merge sort on arrays?
- 1It is O(n²) on already sorted input
- 2It is not stable, so equal keys get reordered
- ✓Correct answer: It needs O(n) extra memory for merging
Explanation
The merge step writes into a temporary buffer. The time is O(n log n) regardless of the input, and the classic implementation is stable. On linked lists merge sort can be done without the extra buffer.