A. Programming Concepts and Skills · Algorithm Design and AnalysisMerge Sort: Divide and Conquer
A3.6 A3.4 C2.3 C2.1About 75 minutes
Learning goals- I can write a merge function that combines two sorted lists in linear time.
- I can write merge sort recursively and trace its splits and merges.
- I can explain why merge sort makes about n log₂ n comparisons and is O(n log n) in every case.
- I can compare merge sort with the O(n²) sorts using counts and run times, including its extra memory.
Words to know
divide and conquer
An algorithm design that splits a problem into smaller parts, solves each part (often recursively), and combines the results.
merge
Combining two sorted lists into one sorted list by repeatedly taking the smaller front element.
merge sort
Sort the left half, sort the right half (recursively), then merge them; a list of 0 or 1 elements is already sorted.
recurrence
An equation that describes a cost in terms of the cost of smaller inputs, e.g. T(n) = 2T(n ÷ 2) + n.
O(n log n)
Linearithmic growth: a little more than linear; for a million items about 20 million steps instead of 10¹² for O(n²).
Two piles of tests
A teacher has two piles of marked tests, each already in alphabetical order. To combine them into one alphabetical pile, she does not start over. She looks at the top test of each pile, takes whichever name comes first, and repeats. When one pile runs out, she puts the rest of the other pile on the end. That is merging, and it takes only one pass.
Now the clever part: if you can merge, you can sort. Split the pile in half, get each half sorted (by the same method!), then merge. This is merge sort, credited to John von Neumann, who described it in 1945. It is the "perform a merge sort" example in expectation A3.6, and it breaks the O(n²) barrier of the sorts you have seen so far.
Step 1: merging two sorted lists
Keep an index into each list. Repeatedly compare the two front elements and append the smaller to the result. When one list is used up, copy what is left of the other.
- Precondition:
left and right are each sorted ascending. - Postcondition: returns a new sorted list containing all their elements; on ties, the element from
left comes first. - Cost: every comparison moves one element into the result, so merging lists with n elements in total takes at most n − 1 comparisons: O(n).
Step 2: merge sort
- Base case: a list of 0 or 1 elements is already sorted.
- Divide: split the list at
mid = len(a) // 2. - Conquer: merge sort each half (recursively).
- Combine: merge the two sorted halves.
def merge(left, right):
"""Merge two sorted lists into one new sorted list.
Precondition: left and right are each sorted ascending.
Postcondition: returns a sorted list of all their elements;
on ties, elements of left come first (stable)."""
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
def merge_sort(a):
"""Return a new sorted list with the elements of a."""
if len(a) <= 1: # base case: already sorted
return a[:]
mid = len(a) // 2
left = merge_sort(a[:mid]) # sort each half recursively
right = merge_sort(a[mid:])
return merge(left, right) # combine
print(merge([3, 27, 38, 43], [9, 10, 82]))
print(merge_sort([38, 27, 43, 3, 9, 82, 10]))
Output, one line each: [3, 9, 10, 27, 38, 43, 82], [3, 9, 10, 27, 38, 43, 82]. The first line merges two sorted lists; the second sorts the seven-element list traced in the diagram below. This version returns a new list and leaves the original unchanged.
Worked exampleTracing the final merge
Trace merge([27, 38, 43], [3, 9, 10, 82]), the last step in the diagram. Count the comparisons.
- Compare 27 and 3: take 3 (from right). Compare 27 and 9: take 9. Compare 27 and 10: take 10. (3 comparisons so far.)
- Compare 27 and 82: take 27 (from left). Compare 38 and 82: take 38. Compare 43 and 82: take 43. (6 comparisons.)
- The left list is used up, so the loop stops. Copy the rest of the right list: 82.
- Result: [3, 9, 10, 27, 38, 43, 82] after 6 comparisons, which is n − 1 for n = 7 (the worst case: the last element of one list is the last to be placed).
[3, 9, 10, 27, 38, 43, 82], with 6 comparisons.
Why is merge sort O(n log n)?
Look at the diagram by levels. At each merge level, every element is merged exactly once, so each level costs about n operations. How many levels? The list is halved until pieces have size 1, which takes about log₂ n halvings. So the total is about
n per level × log₂ n levels = n log₂ n.
As a recurrence: T(n) = 2T(n ÷ 2) + n (two half-size sorts plus a linear merge), with T(1) = 0. Unrolling it for n = 8: T(8) = 2T(4) + 8 = 4T(2) + 16 = 8T(1) + 24 = 24 = 8 × log₂ 8.
Unlike insertion sort, merge sort does the same splitting whatever the input order: its best, average and worst cases are all O(n log n).
import random
comparisons = 0
def merge(left, right):
global comparisons
result = []
i = j = 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
result.extend(left[i:])
result.extend(right[j:])
return result
def merge_sort(a):
if len(a) <= 1:
return a[:]
mid = len(a) // 2
return merge(merge_sort(a[:mid]), merge_sort(a[mid:]))
random.seed(2026)
for n in [1000, 2000, 4000, 8000]:
data = list(range(n))
random.shuffle(data)
comparisons = 0
assert merge_sort(data) == sorted(data)
print(n, comparisons, "insertion sort would need about", n * n // 4)
Output, one line each: 1000 8703 insertion sort would need about 250000, 2000 19434 insertion sort would need about 1000000, 4000 42817 insertion sort would need about 4000000, 8000 93692 insertion sort would need about 16000000. Counting comparisons on shuffled lists. Merge sort's counts stay a little below n log₂ n (about 9966, 21 932, 47 863 and 103 726 for these n), and doubling n only slightly more than doubles them. Insertion sort's average, about n² ÷ 4, quadruples.
Run times
Counting predicts a huge gap; the clock agrees. This program times merge sort against insertion sort on the same random data.
import random, time
def merge(left, right):
result = []
i = j = 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
result.extend(left[i:])
result.extend(right[j:])
return result
def merge_sort(a):
if len(a) <= 1:
return a[:]
mid = len(a) // 2
return merge(merge_sort(a[:mid]), merge_sort(a[mid:]))
def insertion_sort(a):
for i in range(1, len(a)):
key = a[i]
j = i - 1
while j >= 0 and a[j] > key:
a[j + 1] = a[j]
j -= 1
a[j + 1] = key
random.seed(3)
for n in [2000, 4000, 8000, 16000]:
data = [random.random() for _ in range(n)]
start = time.perf_counter()
merge_sort(data)
t_merge = time.perf_counter() - start
copy = data[:]
start = time.perf_counter()
insertion_sort(copy)
t_ins = time.perf_counter() - start
print(n, f"merge {t_merge * 1000:.1f} ms", f"insertion {t_ins * 1000:.1f} ms")
Your times will differ. On one computer: n = 2000: merge 2.8 ms, insertion 67.3 ms; 4000: 6.0 ms and 281.6 ms; 8000: 17.2 ms and 1156.8 ms; 16 000: 29.2 ms and 4865.6 ms. Insertion sort's time quadruples with each doubling; merge sort's roughly doubles (one measurement, 17.2 ms, is noisy).
The costs of merge sort
- Extra memory: merging needs a second list to copy into, so merge sort uses O(n) extra memory. Selection, bubble and insertion sort use O(1). On a small device with little memory, that can matter.
- Stability: using
<= in merge takes from the left list on ties, so equal keys keep their order: merge sort is stable. - Small lists: for tiny lists the recursion and copying overhead make merge sort slower than insertion sort. Real libraries (including Python's Timsort) sort small runs with insertion sort and merge the runs.
- Slicing:
a[:mid] copies half the list at each call. That adds O(n) work per level, which keeps the total at O(n log n). A version that passes low and high indexes and merges into one temporary array avoids the extra copies; you will write it in the challenge. - Recursion depth: only about log₂ n (about 20 for a million items), far below Python's limit.
Another famous divide-and-conquer sort, quicksort, partitions around a "pivot" instead of merging. It sorts in place and is very fast on average, but its worst case is O(n²). You will study it in a first-year university course.
Divide and conquer is a design pattern
Binary search (one half, discard the other), fast power (one half, square it), merge sort (both halves, then merge) and many university algorithms (fast multiplication, closest pair of points) follow the same recipe: divide into smaller subproblems, conquer them recursively, combine the answers. Its cost depends on how many subproblems you make, how big they are, and how expensive the combine step is.
Just for funA merge sort walks into a library with 1 000 000 unsorted books.
It hands half to one friend and half to another, says "Sort these the same way, then bring them back," and goes for a coffee. About 20 levels of friends later, everyone is merging, and the coffee is still warm.
Hands-on activityMerge sort a deck of cards
You need: a deck of playing cards (use 16 cards: Ace to 8 of two suits, Ace = 1), a big table or the floor, and a computer with Python.
- Shuffle the 16 cards and lay them in a row. Split the row into two halves, then each half into halves, until you have 16 single cards (4 splitting levels).
- Merge pairs of single cards into sorted pairs, then pairs into sorted fours, fours into eights, and finally the two eights into one row. Each time, only ever compare the front cards of the two piles.
- Tally every comparison. Theory: never more than n log₂ n = 16 × 4 = 64 (the exact worst case for 16 cards is 49); on average a shuffled deck of 16 takes about 46.
- Now insertion sort the same shuffled order and tally its comparisons. (On average about 73 for 16 cards: one comparison for each shift, about 16 × 15 ÷ 4 = 60, plus about one more per pass to find where the key stops.) Which sort would win by more for 52 cards?
- Add a comparison counter to
merge in Python, sort your starting order, and check your tally.
What to look for: each merge level touches all 16 cards once; for 52 cards merge sort needs at most 52 × log₂ 52 ≈ 296 comparisons, while insertion sort averages about 700 (about 52 × 51 ÷ 4 ≈ 663 shifts plus about one comparison per pass).
Your turn
1Merge [2, 5, 9] and [1, 6, 7, 8]. How many comparisons?
Take 1 (2 vs 1), 2 (2 vs 6), 5 (5 vs 6), 6 (9 vs 6), 7 (9 vs 7), 8 (9 vs 8): 6 comparisons, then copy 9. Result [1, 2, 5, 6, 7, 8, 9], 6 comparisons.
2What is the base case of merge sort, and why is it correct?
A list of length 0 or 1: it is already sorted, so it can be returned as it is.
3For n = 1024, how many levels of merging are there, and about how many comparisons does merge sort make at most?
log₂ 1024 = 10 levels; at most about n log₂ n = 10 240 comparisons.
4Write the recurrence for merge sort's work and solve it for n = 16 (T(1) = 0).
T(n) = 2T(n ÷ 2) + n. T(2) = 2, T(4) = 2 × 2 + 4 = 8, T(8) = 2 × 8 + 8 = 24, T(16) = 2 × 24 + 16 = 64 = 16 × 4.
5Why is merge sort stable?
merge uses <=, so when the front elements are equal it takes the one from the left list, which came first in the original order.
6Give one disadvantage of merge sort compared with insertion sort.
It needs O(n) extra memory; it is not adaptive (no faster on nearly sorted input in this basic form); and it is slower for very small lists.
More practice: warm-up
1What are the three steps of divide and conquer?
Divide, conquer (solve the parts recursively), combine.
2What is the Big-O of merging two sorted lists of total length n?
3What is merge sort's worst-case Big-O?
4Into what two lists does merge sort split [5, 1, 4, 2, 8]?
mid = 5 // 2 = 2: [5, 1] and [4, 2, 8].
5Who invented merge sort, and when?
John von Neumann, in 1945.
More practice: on your own
1Show every split and merge for merge sort on [6, 2, 8, 4].
Split: [6, 2] and [8, 4]; then [6], [2], [8], [4]. Merge: [2, 6] and [4, 8]; then [2, 4, 6, 8].
2What is the smallest possible number of comparisons when merging two sorted lists of 4 elements each? Give an example.
4: if every element of one list is smaller than every element of the other, e.g. [1, 2, 3, 4] and [5, 6, 7, 8]: compare 1, 2, 3, 4 with 5, then copy the rest.
3An O(n log n) sort takes 0.1 s for n = 1 000 000. Estimate the time for n = 2 000 000 and compare with an O(n²) sort that also took 0.1 s at 1 000 000.
n log n: 2 × (21 ÷ 20) ≈ 2.1 times as long: about 0.21 s. n²: 4 times: 0.4 s. The gap widens with each doubling.
4Predict the output:
def merge(left, right):
result = []
i = j = 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:]
``
print(merge(["Ana", "Zoe"], ["Ben", "Kai", "Max"]))
['Ana', 'Ben', 'Kai', 'Max', 'Zoe']. Strings compare alphabetically.
5If merge used < instead of <=, would merge sort still sort correctly? Would it still be stable?
It would still sort correctly (equal elements end up next to each other), but it would not be stable: on ties it would take from the right list first, putting a later element before an earlier equal one.
Challenge
1Write an index-based merge sort msort(a, low, high, temp) that sorts a[low..high] in place using one temporary list, with no slicing.
def msort(a, low, high, temp):
if low >= high:
return
mid = (low + high) // 2
msort(a, low, mid, temp)
msort(a, mid + 1, high, temp)
i, j, k = low, mid + 1, low
while i <= mid and j <= high:
if a[i] <= a[j]:
temp[k] = a[i]; i += 1
else:
temp[k] = a[j]; j += 1
k += 1
while i <= mid:
temp[k] = a[i]; i += 1; k += 1
while j <= high:
temp[k] = a[j]; j += 1; k += 1
for k in range(low, high + 1):
a[k] = temp[k]
Call it as msort(a, 0, len(a) - 1, [None] * len(a)).
2Counting inversions with merge sort: while merging, each time an element is taken from the right list, it is smaller than every element still waiting in the left list. Explain how this counts the inversions of the array in O(n log n), and count them for [3, 1, 2].
When right[j] is taken while left still has len(left) − i elements, right[j] forms an inversion with each of them, so add len(left) − i. Summed over all merges, this counts every inversion exactly once, at no extra Big-O cost. For [3, 1, 2]: split [3] | [1, 2]; [1, 2] has 0. Merging [3] with [1, 2]: take 1 (adds 1), take 2 (adds 1), then 3. Total 2 inversions: (3, 1) and (3, 2).
3Bottom-up merge sort uses no recursion: merge pairs of runs of size 1, then 2, then 4, … Why does it have the same O(n log n) cost? What is its advantage in Python?
It does exactly the same merges as the recursive version, level by level: log₂ n passes, each merging all n elements: O(n log n). Advantage: no recursion, so no call overhead or depth limit, and it is easy to write with loops; it is also how merging of runs works in real libraries.
Quiz
1. What does merge sort do after sorting both halves?
2. What is the worst-case Big-O of merge sort?
3. How many comparisons, at most, to merge two sorted lists with 5 and 6 elements?
4. Which is a real disadvantage of merge sort compared with insertion sort?
5. Solve T(n) = 2T(n ÷ 2) + n with T(1) = 0 for n = 32.
6. Why does merge sort use <= rather than < when merging?
Big idea: "Perform a merge sort" is one of the recursive algorithms named in A3.6, and it is also a sort algorithm (A3.4). Analysing it level by level and with a recurrence, and comparing it with the O(n²) sorts using counts and run times, completes C2.3. The merge function's contract practises C2.1.
How to help: The card activity makes "split until single cards, then merge" concrete. Ask your teen to explain why merging is fast ("you only ever look at the two front cards") and why there are only about log₂ n levels.
Common difficulties:
- Forgetting to copy the leftovers after the merge loop.
- Off-by-one splits (
mid belongs to exactly one half). - Thinking merge sort is O(n log n) "because of the log in binary search" rather than because of levels × work per level.
- Forgetting the O(n) memory cost when comparing sorts.