Which statement about merge sort is correct?
Correct answer A. It is stable and runs in O(n log n) time in every case, but needs O(n) extra space for arrays
Explanation
Merge sort halves the array, sorts each half and merges them; the log n levels each do linear work, so the time is O(n log n) whatever the input. The merge takes from the left half on ties, so equal keys keep their order, making it stable. The price is an auxiliary array of size n, so the standard array version is not in-place.
Answer checked How we write and check questions
Discussion