DSA course menu
Merge Sort in Python: Divide and Conquer Explained
Learn merge sort: splitting a list in half, sorting each half recursively, merging two sorted lists, why it is O(n log n), its O(n) memory cost, and counting inversions with merge sort.
On this page
Merge sort is a divide and conquer algorithm:
- Divide the list into two halves.
- Conquer: sort each half (recursively, with merge sort).
- Combine: merge the two sorted halves into one sorted list.
A list of 0 or 1 items is already sorted: that is the base case.
The merge step#
Merging two sorted lists is the two pointers pattern: repeatedly take the smaller front item. It is O(n) for n items in total.
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:])
result.extend(right[j:])
return result
print(merge([2, 5, 9], [1, 3, 4, 10]))[1, 2, 3, 4, 5, 9, 10]The full algorithm#
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):
print(" " * depth + str(items))
if len(items) <= 1:
return items
mid = len(items) // 2
left = merge_sort(items[:mid], depth + 1)
right = merge_sort(items[mid:], depth + 1)
return merge(left, right)
print(merge_sort([38, 27, 43, 3, 9, 82, 10]))[38, 27, 43, 3, 9, 82, 10]
[38, 27, 43]
[38]
[27, 43]
[27]
[43]
[3, 9, 82, 10]
[3, 9]
[3]
[9]
[82, 10]
[82]
[10]
[3, 9, 10, 27, 38, 43, 82]The indentation shows the recursion splitting the list down to single items; the merges then rebuild it in sorted order on the way back up.
Why O(n log n)?#
Picture the recursion as levels. Halving n down to 1 takes log₂ n levels, and at every level the merges together touch all n items once. So the total work is n × log n.
import math, 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(7)
for n in [1_000, 10_000, 100_000]:
comparisons = 0
data = random.sample(range(10 * n), n)
assert merge_sort(data) == sorted(data)
print(f"n={n:>7}: {comparisons:>9} comparisons, n*log2(n) = {round(n * math.log2(n)):>9}")n= 1000: 8721 comparisons, n*log2(n) = 9966
n= 10000: 120393 comparisons, n*log2(n) = 132877
n= 100000: 1536232 comparisons, n*log2(n) = 1660964The comparison count stays just under n log₂ n and grows at the same rate. For 100,000 items an O(n²) sort would need around 5,000,000,000 comparisons.
The guaranteed O(n log n) and stability make merge sort the basis of Python's Timsort and Java's sort for objects. Its weakness is the O(n) extra memory.
Counting inversions#
An inversion is a pair of items that are out of order (a bigger number before a smaller one). It measures how "unsorted" a list is. Counting pairs directly is O(n²); merge sort counts them in O(n log n): when an item from the right half is taken before items left in the left half, it is smaller than all of them.
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, count = [], 0, 0, a + b
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
count += len(left) - i # right[j] jumps over these
merged += left[i:] + right[j:]
return merged, count
print(sort_and_count([2, 4, 1, 3, 5]))
print(sort_and_count([5, 4, 3, 2, 1]))([1, 2, 3, 4, 5], 3)
([1, 2, 3, 4, 5], 10)[2, 4, 1, 3, 5] has three inversions: (2, 1), (4, 1) and (4, 3).
Common mistakes#
Practice#
Practice exercise
Write merge_k_sorted(lists) that merges any number of sorted lists into one sorted list, by merging them in pairs (like the levels of merge sort) rather than one at a time.
Show hint
While more than one list remains, merge lists 0 and 1, 2 and 3, and so on into a new list of lists. Each round halves the number of lists, so there are log k rounds of O(N) work (N = total items).
Show solution
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_k_sorted(lists):
if not lists:
return []
while len(lists) > 1:
paired = []
for i in range(0, len(lists), 2):
if i + 1 < len(lists):
paired.append(merge(lists[i], lists[i + 1]))
else:
paired.append(lists[i])
lists = paired
return lists[0]
print(merge_k_sorted([[1, 4, 5], [1, 3, 4], [2, 6], [0, 9]]))
print(merge_k_sorted([]))[0, 1, 1, 2, 3, 4, 4, 5, 6, 9]
[]Merging one list at a time into a growing result would cost O(N·k) instead of O(N log k). A heap gives another O(N log k) solution.
Key takeaway#
Next: a faster-in-practice divide and conquer sort, Quick Sort.
Finished this lesson?