Merge Sort

The simple sorts from the previous lesson slow down badly on big lists: doubling the data makes them four times slower. Merge sort is the first algorithm in this course that breaks the O(n²) barrier. It sorts in O(n log n) time in every case, and it is the basis of the sorts used by Python and Java for objects.

In this lesson you will learn the one operation merge sort is built on, merging two sorted lists, then write the full recursive algorithm, prove its running time with a counting experiment and use it to solve a harder problem: counting inversions.

Merging two sorted lists

Two sections of a college in Pune have each sorted their students' marks. To combine them into one sorted list, you do not need to sort again. Keep one finger at the start of each list, take the smaller of the two items under your fingers, and move that finger forward. When one list runs out, copy the rest of the other.

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:          # '<=' keeps the sort stable
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])              # one of these two is empty
    result.extend(right[j:])
    return result

section_a = [45, 62, 78, 91]
section_b = [50, 55, 80, 85, 99]
print(merge(section_a, section_b))
print(merge([], [3, 7]))

[45, 50, 55, 62, 78, 80, 85, 91, 99]
[3, 7]

Each step places one item, so merging lists with a total of n items takes O(n) time. Using <= means that when two items are equal, the one from the left list goes first, which keeps the sort stable.

The merge sort algorithm

Merge sort turns that merge step into a full sort with divide and conquer (see Recursion):

1. Divide: split the list into two halves.
2. Conquer: sort each half by calling merge sort on it. A list of 0 or 1 items is already sorted, which is the base case.
3. Combine: merge the two sorted halves.

def merge(left, right):
    result, i, j = [], 0, 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
    return result + left[i:] + right[j:]

def merge_sort(items, depth=0):
    pad = "   " * depth
    if len(items) <= 1:
        return items
    mid = len(items) // 2
    print(f"{pad}split {items}")
    left = merge_sort(items[:mid], depth + 1)
    right = merge_sort(items[mid:], depth + 1)
    merged = merge(left, right)
    print(f"{pad}merge -> {merged}")
    return merged

merge_sort([38, 27, 43, 3, 9, 82, 10])

split [38, 27, 43, 3, 9, 82, 10]
   split [38, 27, 43]
      split [27, 43]
      merge -> [27, 43]
   merge -> [27, 38, 43]
   split [3, 9, 82, 10]
      split [3, 9]
      merge -> [3, 9]
      split [82, 10]
      merge -> [10, 82]
   merge -> [3, 9, 10, 82]
merge -> [3, 9, 10, 27, 38, 43, 82]

Read the trace from the inside out: the smallest pieces are merged first, then those results are merged into bigger pieces, until the whole list is one sorted piece.

Why it is O(n log n)

Draw the recursion as levels. At the top there is one list of n items. The next level has two lists of n/2, then four lists of n/4, and so on until the lists have one item. Halving n until you reach 1 takes about log₂ n levels. At every level, the merges together touch all n items once, so each level costs O(n). In total: O(n) per level × log n levels = O(n log n).

Let us test that by counting comparisons and comparing with n × log₂ n:

import math
import random

comparisons = 0

def merge(left, right):
    global comparisons
    result, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        comparisons += 1
        if left[i] <= right[j]:
            result.append(left[i]); i += 1
        else:
            result.append(right[j]); j += 1
    return result + left[i:] + right[j:]

def merge_sort(items):
    if len(items) <= 1:
        return items
    mid = len(items) // 2
    return merge(merge_sort(items[:mid]), merge_sort(items[mid:]))

random.seed(1)
for n in [1000, 2000, 4000, 8000]:
    data = random.sample(range(10 * n), n)
    comparisons = 0
    assert merge_sort(data) == sorted(data)
    print(f"n={n:>5}  comparisons={comparisons:>7}  n*log2(n)={round(n * math.log2(n)):>7}  "
          f"insertion sort would need about {n * (n - 1) // 4:>9}")

n= 1000  comparisons=   8715  n*log2(n)=   9966  insertion sort would need about    249750
n= 2000  comparisons=  19412  n*log2(n)=  21932  insertion sort would need about    999500
n= 4000  comparisons=  42815  n*log2(n)=  47863  insertion sort would need about   3999000
n= 8000  comparisons=  93602  n*log2(n)= 103726  insertion sort would need about  15998000

When n doubles, the comparisons grow only a little more than double, exactly the O(n log n) pattern. At 8,000 items, merge sort does under one lakh comparisons where insertion sort needs about 1.6 crore. The assert line checks the result against Python's sorted(), a good habit when you write any sorting code.

The cost of merge sort is memory: the merge step builds new lists, so it needs O(n) extra space. That is the main reason quick sort, which sorts in place, is sometimes preferred.

Bottom-up merge sort

The recursion is not required. Bottom-up merge sort starts by treating every item as a sorted run of length 1, merges neighbouring runs into runs of 2, then 4, then 8, until one run is left. It avoids recursion completely, which is useful in languages or systems with small stacks.

def merge(left, right):
    result, i, j = [], 0, 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
    return result + left[i:] + right[j:]

def merge_sort_bottom_up(items):
    runs = [[x] for x in items]
    while len(runs) > 1:
        paired = []
        for k in range(0, len(runs), 2):
            if k + 1 < len(runs):
                paired.append(merge(runs[k], runs[k + 1]))
            else:
                paired.append(runs[k])       # odd one out waits for the next round
        runs = paired
        print(runs)
    return runs[0] if runs else []

merge_sort_bottom_up([5, 1, 4, 2, 8, 0, 3])

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

This is also the idea behind external sorting: when a file is too big for memory, sort chunks that fit, write them to disk as sorted runs, and merge the runs. Python's heapq.merge() merges any number of already sorted inputs lazily, one item at a time.

Advanced: counting inversions

An inversion is a pair of items that are in the wrong order: a bigger item appears before a smaller one. The number of inversions measures how far a list is from sorted. For example, if a cricket selector ranks five players and the final season statistics rank them differently, the inversions count how many pairs the selector got the wrong way round.

Checking every pair is O(n²). Merge sort can count inversions in O(n log n): during a merge, whenever an item from the right half is taken before the remaining items of the left half, it forms an inversion with every one of those remaining left items.

def sort_and_count(items):
    if len(items) <= 1:
        return items, 0
    mid = len(items) // 2
    left, a = sort_and_count(items[:mid])
    right, b = sort_and_count(items[mid:])
    merged, i, j, cross = [], 0, 0, 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
            cross += len(left) - i       # right[j] beats all remaining left items
    merged += left[i:] + right[j:]
    return merged, a + b + cross

# The selector's order, written as each player's final statistical rank
selector_ranking = [2, 4, 1, 3, 5]
print(sort_and_count(selector_ranking))
print(sort_and_count([5, 4, 3, 2, 1])[1], "inversions in a fully reversed list")

([1, 2, 3, 4, 5], 3)
10 inversions in a fully reversed list

The selector got 3 pairs out of order: (2, 1), (4, 1) and (4, 3). A fully reversed list of 5 has every pair inverted, 5 × 4 / 2 = 10.

Common mistakes

• Forgetting the leftovers. After the main loop, one list still has items. Add left[i:] and right[j:].
• Using < instead of <= in the merge, which makes the sort unstable.
• No base case for an empty list. len(items) <= 1 handles both empty and single-item lists.
• Slicing inside a hot loop. Slices copy; it is fine for learning, but optimised versions pass index ranges instead.

Key points

• Merging two sorted lists of total size n takes O(n) using two pointers.
• Merge sort splits the list in half, sorts each half recursively and merges them.
• There are about log₂ n levels with O(n) work each, giving O(n log n) in every case.
• Merge sort is stable but needs O(n) extra memory.
• Bottom-up merge sort avoids recursion; the merging idea also sorts files bigger than memory.
• A modified merge counts inversions in O(n log n).

import heapq

def merge(left, right):
    result, i, j = [], 0, 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
    return result + left[i:] + right[j:]

a = [1003, 1010, 1042]
b = [1001, 1005, 1050, 1060]
c = [1007, 1044]

print(merge(merge(a, b), c))
print(list(heapq.merge(a, b, c)))

[1001, 1003, 1005, 1007, 1010, 1042, 1044, 1050, 1060]
[1001, 1003, 1005, 1007, 1010, 1042, 1044, 1050, 1060]