Is merge sort stable or unstable, and why?

Is merge sort stable or unstable, and why?

• A. Unstable because equal elements may be reordered during merge.
• B. Stable only if implemented with extra memory
• C. Merge sort is stable because equal elements preserve relative order during the merge.
• D. Stable when the input is already sorted

Answer: (C)

Stability means that equal keys keep their original relative order after sorting. In merge sort, each merge combines two sorted halves while preserving the order within each half. When two elements have the same key, taking the element from the left half first ensures the one that appeared earlier in the input stays before the later equal element in the merged result. Because every merge step does this, equal elements retain their input order throughout the process, so the sort is stable. If you ever took the right element when keys are equal, you’d disrupt that order and lose stability. Stability is a property of the merge process, not of the input being already sorted.

Stability means that equal keys keep their original relative order after sorting. In merge sort, each merge combines two sorted halves while preserving the order within each half. When two elements have the same key, taking the element from the left half first ensures the one that appeared earlier in the input stays before the later equal element in the merged result. Because every merge step does this, equal elements retain their input order throughout the process, so the sort is stable. If you ever took the right element when keys are equal, you’d disrupt that order and lose stability. Stability is a property of the merge process, not of the input being already sorted.