Merge Sort

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.

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.

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.

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.

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)$.

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.