Merge Sort

Merge sort is a divide-and-conquer sorting algorithm: it splits an array in half, recursively sorts each half, and then merges the two sorted halves back together. Unlike quicksort, its performance never degrades on unlucky or already-sorted inputs — it guarantees O(n log n) time no matter what the input looks like. It is also stable, meaning elements that compare equal keep their original relative order, which matters whenever you sort by one field but want to preserve order on another. This lesson covers how merge sort works under the hood, why its complexity is what it is, how to implement it correctly (recursively and iteratively) in Python, and the mistakes that trip people up.

Overview: How Merge Sort Works

Imagine a pile of exam papers you need to sort by score. Instead of scanning the whole pile at once, you split it into two smaller piles, split each of those in half again, and keep going until every pile has exactly one paper. A pile of one paper is trivially “sorted” — there’s nothing to compare. Now you merge piles back together two at a time: to combine two already-sorted piles, you repeatedly look at the top (smallest) paper of each pile and take whichever is smaller, placing it on the new combined pile. Because both input piles are already sorted, you never need to look back — the smallest remaining paper is always at the front of one of the two piles. Keep merging pairs of piles until you’re back to one fully sorted pile.

That is exactly what merge sort does to an array, and it happens in two distinct phases: divide and combine. The divide phase recursively splits the array at its midpoint — not by value, but by index — until each piece has zero or one elements (the base case, since a list of length 0 or 1 is already sorted by definition). The combine phase is the merge step: given two sorted lists, walk two pointers i and j across them, always appending the smaller of the two front elements to a new output list, then appending whatever’s left over once one side runs out.

The key insight for why merge sort’s complexity is so predictable is that it splits by index, not by comparing values (unlike quicksort’s pivot-based partition). That means the split is always perfectly balanced — roughly n/2 and n/2 — regardless of what the data looks like. An already-sorted array, a reverse-sorted array, and a random array all produce the exact same recursion shape: a balanced binary tree of depth log₂ n. That’s why merge sort has no “bad case” the way quicksort does.

Time and Space Complexity

Merge sort’s recursion tree has log₂ n levels, because the array size is halved at each level until it reaches 1. At every level of the tree, the total amount of work done across all the merge calls at that level is O(n) — even though there are more merge calls at deeper levels, each one operates on a proportionally smaller slice, and the sizes always add back up to n per level. Multiplying “O(n) work per level” by “log n levels” gives the overall time complexity.

Case	Time Complexity	Why
Best	O(n log n)	The classic algorithm always fully divides and merges, even on already-sorted input — there’s no early exit.
Average	O(n log n)	The split is always by index (balanced), so a “typical” random input costs the same as any other.
Worst	O(n log n)	Because splitting never depends on data values, there is no adversarial input that unbalances the recursion (unlike quicksort’s O(n²) worst case).

Space: the merge step needs somewhere to build its output while it still reads from the two input halves, so a standard implementation uses O(n) auxiliary space. In the recursive Python version shown below, slicing (arr[:mid]) also allocates new lists at every call, but the recursion unwinds one level at a time, so only O(n) worth of temporary lists are alive at any single moment — plus O(log n) space for the call stack itself. (A true in-place merge sort that avoids the O(n) buffer entirely is possible but significantly more complex and rarely worth it in practice.)

Examples

Example 1: Basic Recursive Merge Sort

def merge_sort(arr: list[int]) -> list[int]:
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left: list[int], right: list[int]) -> list[int]:
    merged = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged

numbers = [38, 27, 43, 3, 9, 82, 10]
sorted_numbers = merge_sort(numbers)
print(sorted_numbers)

Output:

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

The 7-element list splits into [38, 27, 43] and [3, 9, 82, 10]. Each of those recursively splits further until every sub-list has one element, then merge combines pairs back up: [38] and [27, 43] (itself built from [27] and [43]) merge into [27, 38, 43]; on the other side, [3, 9] and [10, 82] merge into [3, 9, 10, 82]. The final call merges [27, 38, 43] with [3, 9, 10, 82], comparing front elements at each step, to produce [3, 9, 10, 27, 38, 43, 82].

Example 2: Stable Sorting Preserves Tie Order

def merge_sort_by_key(arr: list[tuple], key) -> list[tuple]:
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort_by_key(arr[:mid], key)
    right = merge_sort_by_key(arr[mid:], key)
    return merge_by_key(left, right, key)

def merge_by_key(left: list[tuple], right: list[tuple], key) -> list[tuple]:
    merged = []
    i = j = 0
    while i < len(left) and j < len(right):
        if key(left[i]) <= key(right[j]):
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged

students = [("Alice", 85), ("Bob", 72), ("Charlie", 85), ("Dave", 90), ("Eve", 72)]
ranked = merge_sort_by_key(students, key=lambda student: student[1])
print(ranked)

Output:

[('Bob', 72), ('Eve', 72), ('Alice', 85), ('Charlie', 85), ('Dave', 90)]

Bob and Eve both scored 72, and in the original list Bob appears before Eve; in the sorted output Bob still appears before Eve. The same holds for Alice and Charlie, who both scored 85. This is only guaranteed because the merge step uses <= (not <): on a tie, it always takes from the left side first, and the left side was built from earlier positions in the original array. If it used strict <, ties would sometimes flip — see Common Mistakes below.

Example 3: Iterative (Bottom-Up) Merge Sort

def merge(left: list[int], right: list[int]) -> list[int]:
    merged = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged

def merge_sort_iterative(arr: list[int]) -> list[int]:
    width = 1
    result = arr[:]
    n = len(result)
    while width < n:
        for start in range(0, n, 2 * width):
            mid = min(start + width, n)
            end = min(start + 2 * width, n)
            left = result[start:mid]
            right = result[mid:end]
            result[start:end] = merge(left, right)
        width *= 2
    return result

data = [5, 1, 4, 2, 8, 0, 2]
print(merge_sort_iterative(data))

Output:

[0, 1, 2, 2, 4, 5, 8]

Instead of recursing, this version merges adjacent runs of a growing width (1, then 2, then 4, …). With width = 1 it merges single elements into sorted pairs: [5,1]→[1,5], [4,2]→[2,4], [8,0]→[0,8], and the leftover [2] stays as-is, giving [1, 5, 2, 4, 0, 8, 2]. With width = 2 it merges those pairs into runs of four: [1,5] with [2,4] becomes [1,2,4,5], and [0,8] with [2] becomes [0,2,8], giving [1,2,4,5,0,2,8]. With width = 4 the final merge combines [1,2,4,5] with [0,2,8] into the fully sorted [0,1,2,2,4,5,8]. This bottom-up form avoids recursion entirely, which matters for very large inputs since Python’s default recursion limit (around 1000) can make the recursive version raise RecursionError on deep enough call chains.

How Merge Sort Works, Step by Step

Trace merge_sort([8, 3, 5, 1]) by hand:

1. Divide [8, 3, 5, 1] at mid = 2 into [8, 3] and [5, 1].
2. Divide [8, 3] into [8] and [3] — both length 1, so they’re returned as-is (base case).
3. Merge [8] and [3]: compare 8 and 3, take 3 first, then 8 — result [3, 8].
4. Divide [5, 1] into [5] and [1], both base cases.
5. Merge [5] and [1]: take 1 first, then 5 — result [1, 5].
6. Merge [3, 8] and [1, 5]: compare 3 and 1 → take 1; compare 3 and 5 → take 3; compare 8 and 5 → take 5; only 8 remains → take 8. Result: [1, 3, 5, 8].

Notice that no comparison ever happens between elements more than one “pile” apart at a time — the algorithm only ever compares the current fronts of two already-sorted lists, which is what keeps each merge step to a single linear pass.

Common Mistakes

1. Wrong midpoint causes infinite recursion

If you compute the midpoint wrong, the array never actually shrinks, so the base case is never reached:

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr)  # bug: forgot to divide by 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

Here mid equals the full length, so left is a copy of the entire array and right is always empty. The recursive call on left is called with the exact same size every time — it never gets smaller — so Python keeps recursing until it hits the interpreter’s recursion limit and raises RecursionError instead of ever returning a sorted list. The fix is simply dividing by 2:

mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)

2. Using < instead of <= breaks stability

The merge comparison has to use <=, not <, to remain stable:

def merge(left, right):
    merged = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:  # bug: should be <=
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged

With strict <, when left[i] and right[j] are equal, the else branch fires and the element from right is taken first — even though, in the original unsorted array, the element now sitting in left appeared earlier. That silently reorders equal elements, which breaks the stability guarantee that Example 2 above depends on. The fix is using <= so ties always favor the left side, which always corresponds to earlier original positions.

3. Overwriting data during an in-place merge

A tempting “optimization” is merging directly back into the original array without a temporary buffer:

def merge_in_place(arr, start, mid, end):
    i, j = start, mid
    for k in range(start, end):
        if arr[i] <= arr[j]:
            arr[k] = arr[i]
            i += 1
        else:
            arr[k] = arr[j]
            j += 1

The problem is that arr[k], arr[i], and arr[j] all point into the same underlying array. As k advances, it can catch up to and overwrite a position that j still needs to read from later, corrupting values before they’ve been merged. The safe fix is copying the left half into a separate buffer first, so writes into arr never clobber data the algorithm hasn’t read yet:

def merge_in_place(arr: list[int], start: int, mid: int, end: int) -> None:
    left_copy = arr[start:mid]
    i, j, k = 0, mid, start
    while i < len(left_copy) and j < end:
        if left_copy[i] <= arr[j]:
            arr[k] = left_copy[i]
            i += 1
        else:
            arr[k] = arr[j]
            j += 1
        k += 1
    while i < len(left_copy):
        arr[k] = left_copy[i]
        i += 1
        k += 1

Best Practices

• Reach for merge sort when you need a guaranteed worst-case O(n log n) — for example, in latency-sensitive systems where quicksort’s rare O(n²) worst case is unacceptable.
• Reach for merge sort when you need stability — e.g., sorting rows by one column while preserving the existing order from a previous sort on another column.
• Merge sort works well on linked lists, where it can be implemented with O(1) extra space (no random access is needed, unlike quicksort’s partitioning), and on external sorting of data too large to fit in memory, since it naturally processes data in sequential chunks.
• In real Python code, don’t hand-roll merge sort for production use — sorted() and list.sort() use Timsort, a highly optimized, stable hybrid of merge sort and insertion sort that also detects and exploits already-sorted runs. Implement merge sort yourself for learning, interviews, or the specific linked-list/external-sorting cases above.
• When sorting custom objects, pass a key function (as in Example 2) instead of overloading comparison operators — it keeps the merge logic generic and reusable.
• Prefer the iterative (bottom-up) version for very large inputs where recursion depth could approach Python’s recursion limit.

Practice Exercises

1. Modify merge_sort to sort in descending order by changing the comparison in merge. Trace it by hand on [4, 1, 3, 2] before running it, and confirm your code prints [4, 3, 2, 1].
2. Count inversions: An inversion is a pair of indices i < j where arr[i] > arr[j]. Write a modified merge sort that counts inversions while sorting [2, 4, 1, 3, 5]. Hint: every time the merge step takes an element from the right half, it means that element is smaller than all the remaining elements in the left half — add len(left) - i to your inversion count at that moment.
3. Merge k sorted lists: Given [[1, 4, 7], [2, 5], [3, 6, 8, 9]], use the merge function repeatedly (merge the first two, then merge that result with the third, and so on) to produce one fully sorted list. Expected output: [1, 2, 3, 4, 5, 6, 7, 8, 9].

Summary

• Merge sort is a divide-and-conquer, comparison-based sort: divide the array by index until pieces have 0 or 1 elements, then merge sorted pieces back together two at a time.
• Because it always splits evenly by index (not by value), its time complexity is O(n log n) in the best, average, and worst case — there is no adversarial input that degrades it.
• It uses O(n) auxiliary space for the merge buffers, plus O(log n) recursion stack depth in the recursive version.
• Merge sort is stable — equal elements keep their original relative order — but only if the merge comparison uses <=, not <.
• It’s a strong choice for linked lists, external (out-of-core) sorting, and any case needing a guaranteed worst case or stability; in everyday Python code, prefer the built-in sorted()/list.sort() (Timsort), which is a stable merge-sort/insertion-sort hybrid.