Merge Sort Time Complexity: The Viva Answer That Actually Makes Sense

If you've ever answered "why is merge sort O(n log n)" by just saying the words back to an examiner, this is the version that survives a follow-up question.

The two things merge sort does

Merge sort has exactly two moves, and the complexity comes from counting each one separately.

1. Split the array in half, recursively, until each piece has one element.
2. Merge pairs of sorted pieces back together, in order, until you're back to one full array.

Complexity analysis just means: how many splits happen, and how much work does each merge step cost?

Counting the levels — the "log n" part

Start with n elements. Split in half: n/2 and n/2. Split those: n/4 each. Keep halving until you hit pieces of size 1.

How many times can you halve n before you reach 1? That's exactly log₂ n. If n = 16: 16 → 8 → 4 → 2 → 1, that's 4 halvings, and log₂ 16 = 4. This is the whole reason a logarithm shows up at all — it's just "how many times do I divide by 2 to reach 1."

So the recursion tree has log n levels, from the full array at the top down to single elements at the bottom.

Counting the work per level — the "n" part

Now look at just one level of that tree — say, the level where the array is split into 4 pieces of size n/4 each. Merging back up from that level means combining those pieces, and merging two sorted lists of total size k takes O(k) comparisons — you just walk both lists once, taking the smaller front element each time.

Add up the sizes of every piece at any single level, and it always totals n — you've just split the same n elements more ways. So the merging work at each level is O(n), no matter how many pieces that level has.

Put the two together

• log n levels.
• O(n) work at each level.
• Total: O(n) × O(log n) = O(n log n).

That's the whole proof, and it's the version worth saying out loud in a viva instead of the memorized line — because it survives "okay, but why log n specifically" without you freezing.

The follow-ups examiners actually ask

"What about best case and worst case?" Merge sort doesn't have a best/worst case split — it's O(n log n) in all three (best, average, worst), because it always splits the array the same way regardless of what the data looks like. That's different from quicksort, where a bad pivot choice can degrade it to O(n²).

"What about space complexity?" O(n) — merge sort needs a temporary array to merge into, unlike an in-place sort like heapsort. This is the standard trade-off examiners want you to name: merge sort trades extra memory for a guaranteed O(n log n), no matter how the input is arranged.

"Is it stable?" Yes — if you write the merge step to prefer the left array's element on ties, equal elements keep their original relative order. This matters if you're sorting records by one field but want a previous sort order preserved as the tiebreaker.

---

Sumantrak is an AI mentor built for Indian engineering, diploma, BCA and BSc CS/IT students — DSA, DBMS, and the rest of your syllabus, explained the way this page just did it. Free to start →