Why Is Mergesort Always O(n log n) and Stable?

Mergesort is a classic divide-and-conquer sorting algorithm that guarantees worst-case logarithmic-linear time complexity while preserving the relative order of equal elements. Unlike algorithms whose performance depends on input distribution, Mergesort achieves this consistent efficiency by always splitting the input in half and merging sorted subarrays deterministically.

Guaranteed \(O(n \log n)\) Time Complexity

Mergesort divides an array of size \(n\) into two halves of size \(\lfloor n/2 \rfloor\) and \(\lceil n/2 \rceil\), recursively sorts each half, and then merges the two sorted halves back together. Because the split is always balanced regardless of the input values, the algorithm's running time is governed by the recurrence relation:

\[T(n) = 2T\left(\frac{n}{2}\right) + \Theta(n)\]

By the Master Theorem (or by analyzing the recursion tree), we can see why this always resolves to \(\Theta(n \log n)\):

  1. Tree Depth: Dividing \(n\) by \(2\) at each step produces a binary recursion tree of height \(\lceil \log_2 n \rceil\).
  2. Work Per Level: At each level \(k\) of the tree, there are \(2^k\) subproblems, each of size \(n / 2^k\). Merging all pairs at level \(k\) requires scanning every element once, which takes \(\Theta(n)\) total time per level.
  3. Total Work: Multiplying the \(\Theta(n)\) work per level by the \(\Theta(\log n)\) levels yields a total time complexity of \(\Theta(n \log n)\) in the best, average, and worst cases.

Even if the input is already sorted, reverse-sorted, or contains many duplicates, the number of splits and merges remains the same, guaranteeing an \(O(n \log n)\) upper bound.

Preserving Relative Order as a Stable Sort

A sorting algorithm is stable if two elements with equal keys appear in the same relative order in the sorted output as they did in the original input. Mergesort achieves stability through a simple rule during the merge step.

When merging a sorted left subarray \(L\) and a sorted right subarray \(R\), the algorithm compares the current front elements \(L[i]\) and \(R[j]\):

  • If \(L[i] \le R[j]\), the element \(L[i]\) is placed into the output array, and \(i\) is incremented.
  • Otherwise (\(L[i] > R[j]\)), the element \(R[j]\) is placed into the output array, and \(j\) is incremented.

Because every element in \(L\) originally appeared before every element in \(R\), using the non-strict inequality (\(\le\)) ensures that when \(L[i] = R[j]\), the element from \(L\) is always chosen first. Since recursive calls on \(L\) and \(R\) are themselves stable, this tie-breaking rule preserves the original relative order of all equal elements across the entire array.