Which is true about merge sort?
Options
- It sorts in place with O(1) memory, but it is not stable
- It is stable, O(n log n) always, and needs O(n) extra space (Correct option)
- Its worst case is O(n²) when the input is nearly sorted
- It only works on linked lists, never on plain arrays
Answer
Stable, O(n log n) in all cases, O(n) extra space for arrays
Why
Merge sort splits the list in halves until single items remain, then merges sorted halves back together. Every level takes O(n) work and there are log n levels: O(n log n), always.
Merging needs a temporary array: O(n) extra memory.
It is stable: equal items keep their original order, which matters when you sort by one field after another.
Remember
Merge sort = always O(n log n), stable, needs extra memory.