Course contentsShow
← Computer Science
Lesson 758 of 2,87218. Sorting AlgorithmsFree lesson

Mergesort Stability

Explaining why mergesort is a stable sort and how equal elements maintain their relative order.

Mergesort Stability

You'll learn: Why mergesort preserves the original order of equal elements, making it a stable sorting algorithm.

What Makes a Sort Stable?

Recall that a stable sort maintains the relative order of elements with equal keys. If two elements compare as equal, whichever appeared first in the original array stays first in the sorted result.

Why Mergesort is Stable

Mergesort's stability comes directly from how the merge operation handles equal elements. When merging two sorted subarrays, you compare elements from the left and right halves. The key is what happens when they're equal:

The stable implementation rule: When elements are equal during merge, always take from the left subarray first.

Since the left subarray represents elements that came earlier in the original sequence (due to how the array was divided), taking from the left preserves their original relative order.

Simple Example

Imagine sorting pairs by their first number:

Original: (3,a) (1,b) (3,c) (2,d)

During merges, when (3,a) and (3,c) are compared, (3,a) came first originally and sits in the left subarray. By taking from the left when equal, (3,a) appears before (3,c) in the result:

Sorted: (1,b) (2,d) (3,a) (3,c)

Notice (3,a) still precedes (3,c) — their relative order is preserved.

The Bottom Line

Mergesort achieves stability not through extra work, but through a simple, consistent rule in the merge step: favor the left when equal. This makes mergesort ideal when stability matters, such as sorting database records by multiple fields sequentially.

Key Takeaway: Mergesort is stable because the merge operation always takes from the left subarray first when elements are equal, preserving their original relative order.