Introduction

Merge sort is a classic sorting algorithm that works by repeatedly splitting a list into smaller pieces and then merging those pieces back together in order. It is popular because it is reliable, predictable, and much faster on large inputs than simple quadratic algorithms such as bubble sort.

If recursion feels abstract, the easiest way to understand merge sort is to think of it as two separate jobs: break the list into tiny sorted pieces, then combine those sorted pieces carefully.

The Big Idea: Split, Then Merge

Suppose you want to sort this list:

[38, 27, 43, 3, 9, 82, 10]

Merge sort keeps splitting it:

1[38, 27, 43, 3, 9, 82, 10]
2[38, 27, 43]   [3, 9, 82, 10]
3[38] [27, 43]  [3, 9] [82, 10]
4[38] [27] [43] [3] [9] [82] [10]

At that point, every one-element list is already sorted. Then merge sort starts building back up:

1[27, 43]
2[3, 9]
3[10, 82]
4[27, 38, 43]
5[3, 9, 10, 82]
6[3, 9, 10, 27, 38, 43, 82]

The clever part is the merge step. Because each half is already sorted, you only need to compare the front elements of the two halves to build the final sorted result.

How the Merge Step Works

Imagine merging these two sorted lists:

left  = [3, 9, 27]
right = [10, 38, 43]

Compare the first elements:

• '3 versus 10, so take 3'
• '9 versus 10, so take 9'
• '27 versus 10, so take 10'
• '27 versus 38, so take 27'
• then append the remaining values 38 and 43

Result:

[3, 9, 10, 27, 38, 43]

Because the two halves were already sorted, the merge step is linear and efficient.

A Simple Python Implementation

Here is a complete recursive version:

1def merge_sort(values: list[int]) -> list[int]:
2    if len(values) <= 1:
3        return values
4
5    middle = len(values) // 2
6    left = merge_sort(values[:middle])
7    right = merge_sort(values[middle:])
8
9    return merge(left, right)
10
11
12def merge(left: list[int], right: list[int]) -> list[int]:
13    result = []
14    i = 0
15    j = 0
16
17    while i < len(left) and j < len(right):
18        if left[i] <= right[j]:
19            result.append(left[i])
20            i += 1
21        else:
22            result.append(right[j])
23            j += 1
24
25    result.extend(left[i:])
26    result.extend(right[j:])
27    return result
28
29
30numbers = [38, 27, 43, 3, 9, 82, 10]
31print(merge_sort(numbers))

This prints:

[3, 9, 10, 27, 38, 43, 82]

Notice that the function returns a new sorted list rather than modifying the input in place.

Why Merge Sort Is Fast

Merge sort has O(n log n) time complexity in the best, average, and worst cases. That predictability is one of its biggest strengths.

Why n log n? Each level of recursion processes all n elements during merging, and there are about log n levels of splitting.

It also has an important practical property: stability. If two elements compare equal, merge sort can preserve their original relative order. That matters when you sort records by one key and want ties to keep an earlier ordering.

Common Pitfalls

• Thinking the splitting step sorts the data by itself. Splitting only prepares the data for merging.
• Forgetting that merge sort usually needs extra memory for temporary arrays or lists.
• Writing the merge loop with off-by-one mistakes and losing the remaining elements from one half.
• Assuming recursion is free. Very large recursive implementations can add overhead or hit recursion limits in some languages.
• Using merge sort everywhere. It is great for predictable performance, but another algorithm may be better depending on memory constraints or data layout.

Summary

• Merge sort splits a list into small sorted pieces and merges them back together.
• The merge step is efficient because it combines two already-sorted halves.
• Its runtime is O(n log n) in all major cases.
• It is stable and well suited to large datasets.
• If the recursive idea feels confusing, focus on the merge step first; that is where the algorithm does its real work.