Introduction

Merge sort is a recursive divide-and-conquer algorithm, and most of the confusion comes from not seeing how the recursive calls and merge steps interleave. The key mental model is that merge sort does not sort while going down the recursion tree; it sorts while coming back up.

The Three Steps In Every Call

Every merge sort call does the same three things:

1. stop if the list has length 0 or 1
2. split the list into two halves
3. recursively sort both halves and then merge them

That means recursion is not incidental to merge sort. It is the mechanism that keeps breaking the problem into smaller sortable pieces.

Here is the standard version:

1def mergesort(arr):
2    if len(arr) <= 1:
3        return arr
4
5    mid = len(arr) // 2
6    left = mergesort(arr[:mid])
7    right = mergesort(arr[mid:])
8    return merge(left, right)
9
10
11def merge(left, right):
12    result = []
13    i = j = 0
14
15    while i < len(left) and j < len(right):
16        if left[i] <= right[j]:
17            result.append(left[i])
18            i += 1
19        else:
20            result.append(right[j])
21            j += 1
22
23    result.extend(left[i:])
24    result.extend(right[j:])
25    return result

What The Recursion Tree Looks Like

Take the input [7, 2, 9, 1].

The recursive splitting phase is:

• '[7, 2, 9, 1]'
• '[7, 2] and [9, 1]'
• '[7], [2], [9], and [1]'

At that point, recursion has reached the base case. Single-element lists are already sorted.

Then the merging phase begins while the call stack unwinds:

• merge [7] and [2] into [2, 7]
• merge [9] and [1] into [1, 9]
• merge [2, 7] and [1, 9] into [1, 2, 7, 9]

That is the crucial idea: the recursive descent only splits. The actual ordering work happens on the way back up.

Trace The Calls To See It Clearly

A trace function makes the call stack visible.

1def mergesort_trace(arr, depth=0):
2    indent = "  " * depth
3    print(f"{indent}call: {arr}")
4
5    if len(arr) <= 1:
6        print(f"{indent}return base: {arr}")
7        return arr
8
9    mid = len(arr) // 2
10    left = mergesort_trace(arr[:mid], depth + 1)
11    right = mergesort_trace(arr[mid:], depth + 1)
12    merged = merge(left, right)
13
14    print(f"{indent}return merged: {merged}")
15    return merged
16
17
18mergesort_trace([4, 1, 3, 2])

Reading that output is often the fastest way to understand the recursion. You can see the stack deepen until the base case, then return merged values step by step.

Why The Base Case Matters

The base case len(arr) <= 1 is what stops the recursion. Without it, merge sort would keep splitting forever.

A list of length 1 is already sorted, so recursion has reached the smallest subproblem that needs no more work.

That is a common pattern in recursive algorithms:

• reduce the problem size
• stop at a trivial solvable case
• combine returned sub-results

Merge sort is a clean example of that structure.

Time And Space From The Recursion Structure

Recursion also explains merge sort's complexity.

Each level of the recursion tree processes all n elements during merging. The tree has about log n levels because the list is halved each time. That gives total time complexity of O(n log n).

The recursive version also uses extra space:

• temporary arrays or lists during merging
• stack frames from recursive calls

That is why merge sort is efficient and predictable, but not usually in-place in its simplest form.

Stability Comes From The Merge Logic

Merge sort is commonly stable, meaning equal elements keep their original relative order. That depends on the merge step.

In the code above, the comparison uses <=, which prefers the left element when two values are equal. That preserves the original ordering across equal values.

This detail is small, but it matters in real applications that sort records by multiple keys.

Common Pitfalls

The most common mistake is imagining that each recursive call sorts its half immediately. It does not. Each call first delegates more splitting to deeper calls.

Another mistake is forgetting that merge sort returns sorted sublists, not sorted indices or partial side effects in the simple functional version.

Developers also often get the merge step wrong by failing to append the remaining tail of one half after the main loop finishes.

Finally, do not lose sight of the base case. If the stopping condition is wrong, the recursion structure collapses.

Summary

• Merge sort uses recursion to split the list until trivial base cases are reached.
• The algorithm sorts during stack unwinding, not during recursive descent.
• The merge step is where ordered sublists are combined into larger ordered lists.
• The recursion tree explains the O(n log n) time complexity.
• A correct base case and a correct merge function are the core of the algorithm.