Why Is Merge Sort N Log N? | The Real Reason It Scales

You’ll hear “merge sort is n log n” so often that it starts to feel like a rule of nature. Still, if you’ve ever tried to justify it in plain words, it can get slippery. Where does the log come from? Why doesn’t the merge step blow things up to n²? Why does the work per level stay flat?

This article answers those questions in a way you can repeat in an interview, a classroom, or your own notes. We’ll pin down where each piece of the cost comes from, then prove it using two standard tools: a recursion tree and the Master Theorem. You’ll leave with a mental model that sticks.

What “N Log N” Means In One Sentence

When people say merge sort is “n log n,” they’re describing how the number of operations grows as the input size grows.

• The n part: merging touches each item a constant number of times per merge pass.
• The log n part: splitting in half creates about log₂(n) layers of recursion.

Put them together: “n work per layer” times “log n layers” gives n·log n.

What Merge Sort Actually Does

Merge sort has two phases that repeat until the pieces are tiny.

Phase 1: Split

Take the array (or list), split it into two halves, then split each half again. Keep going until you reach subarrays of length 1 (or 0). A length-1 list is already sorted, so recursion stops there.

Phase 2: Merge

Now rebuild upward. At each step, you merge two sorted halves into one sorted whole by walking two pointers forward and copying the smaller item each time. This merge step is where the real work happens.

Here’s the first anchor idea: the split step is cheap. The merge step is the bill you pay each time you come back up a level.

Why The Merge Step Is Linear

Let’s focus on merging two sorted arrays whose total length is n. The merge routine moves through the data once. Each comparison advances one pointer, and each element gets copied exactly once into the output buffer.

That’s why merge is Θ(n) for a combined length of n. No tricks. No hidden loops. Just a straight pass.

If you want a quick external reference for merge sort’s runtime claim, Stanford’s CS106B lecture notes summarize it cleanly here: CS106B sorting lecture notes.

Why Is Merge Sort N Log N? With A Recursion-Tree Walkthrough

Now we stitch it together. Merge sort splits the input into halves until it reaches size 1. That halving pattern is where the log shows up.

Step 1: Count The Levels

Start with n items. After one split, you have subproblems of size n/2. After two splits, size n/4. After k splits, size n/2ᵏ.

You stop when the subproblem size becomes 1:

n / 2ᵏ = 1

That implies 2ᵏ = n, so k = log₂(n).

So the recursion has about log₂(n) levels. That’s the second anchor idea.

Step 2: Measure Work Per Level

At the bottom, you start merging tiny sorted pieces. As you go up, the merges get bigger, yet the total merged length across the whole level stays the same.

Here’s the part that clears the fog: at any fixed level, the subarrays at that level form a partition of the original array. They don’t overlap. Their lengths add up to n.

Since merging is linear in the merged length, the total merge work across that entire level is Θ(n). It doesn’t matter if the level contains many small merges or a few large merges. Sum of lengths is still n.

Step 3: Multiply

Each level costs Θ(n). There are Θ(log n) levels. Multiply them:

Θ(n) × Θ(log n) = Θ(n log n)

That’s the whole story in three moves: count levels, sum work per level, multiply.

The Recurrence That Encodes The Same Idea

If you like formulas, merge sort’s runtime can be written as a recurrence:

• You solve two subproblems of size n/2 → 2T(n/2)
• You merge the results in linear time → + Θ(n)

So:

T(n) = 2T(n/2) + Θ(n)

The recursion tree explanation you just read is the “shape” of this recurrence turned into a picture.

If you want a solid, official-style refresher on recurrences as a concept (not just this one), MIT OpenCourseWare has a clear lecture PDF you can skim: MIT OCW lecture on recurrences.

Table: Where The N·Log₂N Comes From Level By Level

This table shows the recursion-tree view when n is a power of two. The “total merge work” column is the punchline: it stays at n each level, then repeats for log₂(n) levels.

Recursion Level	Pieces At This Level	Total Merge Work
0	1 piece of size n	n
1	2 pieces of size n/2	2 × (n/2) = n
2	4 pieces of size n/4	4 × (n/4) = n
3	8 pieces of size n/8	8 × (n/8) = n
4	16 pieces of size n/16	16 × (n/16) = n
5	32 pieces of size n/32	32 × (n/32) = n
6	64 pieces of size n/64	64 × (n/64) = n
log₂(n)	n pieces of size 1	stop (already sorted)

Read the “Total Merge Work” column top to bottom: n, n, n, n… repeated about log₂(n) times. That repetition is your n·log n.

Why Is Merge Sort N Log N? Master-Theorem Version

If you want a fast proof without drawing a tree, use the Master Theorem on the recurrence:

T(n) = aT(n/b) + f(n)

For merge sort:

• a = 2 (two subproblems)
• b = 2 (each is half size)
• f(n) = Θ(n) (merge step)

Compute n^(log_b a):

n^(log₂ 2) = n^1 = n

So f(n) matches n^(log_b a). That lands in the “balanced” case, which yields:

T(n) = Θ(n log n)

This proof is short because the theorem packages the recursion-tree logic into a reusable rule. You still want the tree intuition, since it explains why the theorem applies and what “balanced” really means in plain terms.

What About Non-Powers Of Two?

Real inputs aren’t always powers of two, and merge sort still lands at Θ(n log n).

When n is odd, the split becomes ⌊n/2⌋ and ⌈n/2⌉. That changes the sizes by at most 1. The recursion depth stays proportional to log n because repeated halving still reaches 1 in that many steps.

The merge cost stays linear in the combined size. Since the pieces at any one level still partition the array, the total merged length at that level stays near n. Same story, with small rounding noise that doesn’t change the growth rate.

Worst Case, Best Case, And Why Merge Sort Stays Steady

Some sorts speed up on already-sorted input. Merge sort doesn’t care. It splits the array the same way every time, then merges the same sizes every time.

That makes its runtime steady across input patterns:

• Worst case: Θ(n log n)
• Average case: Θ(n log n)
• Best case: Θ(n log n)

That predictability is a real plus when you want stable performance. It’s also why merge sort is a frequent building block in systems code and in sorting linked lists, where the merge step is especially natural.

Space Cost: Why Merge Sort Uses Extra Memory

Classic merge sort needs an auxiliary array (or buffer) during merging. In the common array implementation, that buffer is proportional to n, so auxiliary space is O(n).

There’s also the recursion stack. Since the depth is O(log n), stack space adds O(log n) frames. In practice, the buffer dominates.

Some variants reduce extra memory by doing more complex in-place merging, yet those versions are trickier and can be slower in real code because they trade simple sequential writes for more pointer chasing and data movement.

Common Confusions That Cause Bad “Proofs”

“There Are Log N Levels, So It’s Just Log N”

Counting levels alone ignores the work done at each level. Each level still merges through the data. That level cost is the n part.

“Merging Two Halves Is N/2, So Each Level Is N/2”

A single merge at a level might be n/2 or n/4, yet there are multiple merges at that level. Add them up across the level and you’re back at n.

“It’s N Log N Because It Splits And Merges”

This is the right vibe, yet it’s not a reason. The reason is: halving creates log₂(n) levels, and merging across any level touches n items in total.

Table: Three Ways To Justify Merge Sort’s Runtime

All three routes land on Θ(n log n). Pick the one that matches your setting: whiteboard, homework proof, or quick recall.

Method	What You Track	Why It Lands On n·log n
Recursion tree	Work per level	Each level sums to n, and there are log₂(n) levels
Master Theorem	a, b, and f(n)	2T(n/2)+n matches the balanced case → n log n
Substitution	Upper/lower bounds	Assume T(n) ≤ cn log n, expand recurrence, then close the inequality
Level-sum view	Total merged length	Partitions at each level still cover the array once

A Short Mental Model You Can Reuse

If you want a single line to carry around in your head, use this:

“Merge sort does a full linear merge pass per level, and the number of levels is the number of times you can halve n until you hit 1.”

That line explains the n and the log without hand-waving. It’s also portable to other divide-and-conquer algorithms. Swap out the “merge pass is linear” part and you can estimate runtimes for a lot of recursive patterns.