---
title: 'Merge Sort'
source: 'https://academia.sh/en/courses/algorithms/merge-sort'
course: Algorithms
language: en
updated: '2026-08-17T18:07:43+00:00'
license: 'CC BY-SA 4.0'
---

# Merge Sort

Stable sorting with divide and conquer, the correctness of the merge operation, the bottom-up variant, external sorting, and counting inversions.

Quadratic algorithms cannot be used on data in the millions. The recurrence solved in
the Method for Computing Complexity lesson already pointed to the way out:

$$
T(n) = 2\,T(n/2) + O(n) \implies T(n) = O(n \log n)
$$

This lesson builds the algorithm that produces that recurrence: split the array in
two, sort each half, merge the two sorted halves.

## The Merge

The algorithm's core is **merging two sorted arrays into one sorted array**. Two
pointers are used; the smaller one is taken at every step.

```python
def merge(left: list[int], right: list[int]) -> list[int]:
    """Merges two sorted arrays into one sorted array.

    Invariant: the result is the sorted form of the elements taken from the two
    arrays so far, and every element not yet taken is not less than every element
    already in the result.
    """
    result: list[int] = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:         # left takes priority on equality: stability
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])             # once one is exhausted, the remainder of the other is appended
    result.extend(right[j:])
    return result


print(merge([1, 5, 9], [2, 5, 6]))     # [1, 2, 5, 5, 6, 9]
```

The merge is $O(n)$: every element is taken exactly once and never looked at again.

The `<=` sign is the source of stability. On equality, the element on the left — the
one that came first in the input — is chosen. Writing `<` would make the algorithm
lose its stability; this is one of the examples where a one-character difference
determines a behavioral property.

## Divide and Conquer

What remains is only the recursive frame.

```python
def merge_sort(array: list[int]) -> list[int]:
    if len(array) <= 1:                 # base case: zero or one element is already sorted
        return list(array)
    mid = len(array) // 2
    left = merge_sort(array[:mid])
    right = merge_sort(array[mid:])
    return merge(left, right)


print(merge_sort([5, 2, 9, 1, 5, 6]))      # [1, 2, 5, 5, 6, 9]
print(merge_sort([]))                      # []
print(merge_sort([3, 3, 3]))               # [3, 3, 3]
```

Its correctness is justified by induction: the base case is correct; if both halves
are correctly sorted, the merge operation also produces a correctly sorted array.
Termination comes from the subproblems shrinking with certainty — the `mid`
computation ensures neither part is empty.

## Cost

At every level of the recursion tree, a total of $n$ units of merge work are done,
and the number of levels is $\log_2 n$. Because the split is made without looking at
the input's content, this is the same **in every case**:

| Case | Comparisons | Class |
|---|---|---|
| Best | $\sim \frac{n \log_2 n}{2}$ | $\Theta(n \log n)$ |
| Average | $\sim n \log_2 n$ | $\Theta(n \log n)$ |
| Worst | $\sim n \log_2 n$ | $\Theta(n \log n)$ |

The same cost regardless of the input — this guarantee is a property the quicksort of
the next lesson does not have.

Space cost is the algorithm's weak point: the merge uses an $O(n)$ extra array for
the result. Added to this is the recursion stack's $O(\log n)$ depth. In-place merge
variants working on the array exist, but their constants are large and they
complicate the code.

```python
def counted_sort(array: list[int]) -> tuple[list[int], int]:
    """(sorted array, comparison count)"""
    if len(array) <= 1:
        return list(array), 0
    mid = len(array) // 2
    left, a = counted_sort(array[:mid])
    right, b = counted_sort(array[mid:])
    result: list[int] = []
    i = j = count = 0
    while i < len(left) and j < len(right):
        count += 1
        if left[i] <= right[j]:
            result.append(left[i]); i += 1
        else:
            result.append(right[j]); j += 1
    result.extend(left[i:]); result.extend(right[j:])
    return result, a + b + count


import math
for n in (16, 1024, 65_536):
    data = [(i * 7919) % n for i in range(n)]        # regular but unsorted input
    print(n, counted_sort(data)[1], int(n * math.log2(n)))

# 16 35 64
# 1024 8929 10240
# 65536 956515 1048576
```

The measured comparison count stays below the $n \log_2 n$ estimate; because when one
array in a merge is exhausted early, the remaining elements are transferred without
comparison, the actual count falls slightly under the bound. The order of magnitude
is the same.

## The Bottom-Up Variant

The same algorithm can be written without recursion: single-element blocks are
merged two at a time first, then pairs, then groups of four.

```python
def bottom_up_merge_sort(array: list[int]) -> list[int]:
    d = list(array)
    width = 1
    while width < len(d):
        for start in range(0, len(d), 2 * width):
            mid = min(start + width, len(d))
            end = min(start + 2 * width, len(d))
            d[start:end] = merge(d[start:mid], d[mid:end])
        width *= 2
    return d


print(bottom_up_merge_sort([5, 2, 9, 1, 5, 6]))        # [1, 2, 5, 5, 6, 9]
print(bottom_up_merge_sort([4, 3, 2, 1]))              # [1, 2, 3, 4]
```

The result is the same, and no stack space is spent. An adaptive variant, instead of
single-element blocks, treats the **runs** already sorted in the input as the
starting blocks; this reduces the number of levels on nearly sorted data.

## Working with Sequential Access

The merge accesses elements from start to end in a single direction; it does not
require random access. This property is decisive in two areas.

**In linked lists.** Reaching the middle element in the linked list from the Data
Structures course is linear, but the merge is done just by redirecting links. This is
the sort preferred in practice for linked lists, and it requires no extra array.

**In external sorting.** If the data does not fit in memory, chunks are loaded into
memory one at a time, sorted, and written to disk, and the sorted chunks are then
merged as a stream. Because the merge reads in a single direction, it makes
sequential reading over disk or network possible — a direct consequence of the
locality principle from the How Computers Work course.

## Counting Inversions

In the previous lesson, the inversion count was computed by brute force in
$O(n^2)$. During a merge, every time an element from the right is taken ahead of one
from the left, it forms an inversion with **every remaining element on the left**;
this observation brings the count down to $O(n \log n)$.

```python
def fast_inversion_count(array: list[int]) -> tuple[list[int], int]:
    if len(array) <= 1:
        return list(array), 0
    mid = len(array) // 2
    left, a = fast_inversion_count(array[:mid])
    right, b = fast_inversion_count(array[mid:])
    result: list[int] = []
    i = j = count = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i]); i += 1
        else:
            result.append(right[j]); j += 1
            count += len(left) - i       # all remaining elements on the left form an inversion
    result.extend(left[i:]); result.extend(right[j:])
    return result, a + b + count


print(fast_inversion_count([5, 2, 9, 1, 5, 6])[1])      # 6
print(fast_inversion_count([5, 4, 3, 2, 1])[1])         # 10
print(fast_inversion_count(list(range(1000)))[1])       # 0
```

The results are the same as the brute-force count. This is the first example of the
divide-and-conquer idea being used beyond sorting: a small addition to the merge step
computes an entirely different quantity.

## Summary

- Merge sort splits the array in two, sorts the halves, and merges the sorted halves
  at linear cost.
- Choosing the left element on equality during the merge provides stability.
- Cost is $\Theta(n \log n)$ in every case; the split does not depend on the input's
  content.
- Extra space is $O(n)$; this is the algorithm's main cost.
- The bottom-up variant removes the recursion stack; the run-based variant adds
  adaptivity.
- Because it works with sequential access, it is preferred for linked lists and
  external sorting.

## Next Step

Merge sort is safe but requires extra space. The next lesson covers quicksort, which
achieves the same linearithmic order while operating in place — at the cost of
losing the worst-case guarantee. How pivot selection turns this loss into a matter of
probability will be at the center of the lesson.