Merge Sort and Counting Inversions
30 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)Merge sort turns a hard problem into two smaller ones plus a cheap merge. It is the standard answer when you need a guaranteed O(n log n) and a stable sort, and its merge step also counts inversions.
Divide, sort, merge
Merge sort is a divide and conquer sort that splits a list in halves, sorts each half by the same method, and merges the two sorted halves into one sorted list.
Split the list in half, sort each half the same way, then merge the two sorted halves into one. A list of one item is already sorted, which stops the splitting.
def merge_sort(items): if len(items) <= 1: return items mid = len(items) // 2 left = merge_sort(items[:mid]) right = merge_sort(items[mid:]) return merge(left, right)Example 1 · Watch the splits and merges
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 print(pad + "split", items) if len(items) <= 1: return items mid = len(items) // 2 merged = merge(merge_sort(items[:mid], depth + 1), merge_sort(items[mid:], depth + 1)) print(pad + "merged", merged) return merged
merge_sort([6, 2, 8, 4])split [6, 2, 8, 4]
split [6, 2]
split [6]
split [2]
merged [2, 6]
split [8, 4]
split [8]
split [4]
merged [4, 8]
merged [2, 4, 6, 8]What this code does
- The indentation shows the depth of the recursion. The list of 4 is split twice, then merged back twice.
- Python slices
items[:mid]copy the data, which is where the O(n) extra space comes from.
The function calls itself on smaller lists. The real work happens in merge, shown next.
The merge step
Keep one pointer in each sorted half. Copy the smaller front value into the result and move that pointer. When one half 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]: result.append(left[i]) i += 1 else: result.append(right[j]) j += 1 result.extend(left[i:]) result.extend(right[j:]) return resultExample 2 · Merge two sorted lists with heapq
import heapq
morning = [2, 5, 9]evening = [1, 5, 8, 12]print(list(heapq.merge(morning, evening)))[1, 2, 5, 5, 8, 9, 12]
What this code does
heapq.mergedoes the merge step lazily for any number of sorted inputs.- Interviewers still expect the hand-written two-pointer merge, so know both.
Example 3 · Ties and stability
def merge_by_mark(left, right): result, i, j = [], 0, 0 while i < len(left) and j < len(right): if left[i][1] <= right[j][1]: result.append(left[i]) i += 1 else: result.append(right[j]) j += 1 return result + left[i:] + right[j:]
first = [("Asha", 70), ("Ben", 80)]second = [("Chen", 70), ("Dev", 90)]print([name for name, mark in merge_by_mark(first, second)])['Asha', 'Chen', 'Ben', 'Dev']
What this code does
- Asha and Chen both have 70. The left list wins ties, so Asha comes first.
- Changing
<=to<would put Chen first and make the sort unstable.
Using <= takes the left value on a tie, so equal items keep their order and the sort is stable. Merging n items costs O(n).
Why it is O(n log n)
Halving a list of n items takes about log n levels, and each level merges n items in total. So the time is O(n log n) in every case, with O(n) extra space for the merged lists.
Example 4 · The work grows like n log n
work = 0
def merge_sort(items): global work if len(items) <= 1: return items mid = len(items) // 2 left, right = merge_sort(items[:mid]), merge_sort(items[mid:]) merged, i, j = [], 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 merged += left[i:] + right[j:] work += len(merged) return merged
merge_sort(list(range(1024, 0, -1)))print(work)10240
What this code does
- Counting every value written during merges gives 1024 * 10: ten levels, 1024 values each.
- A list of 1024 items would cost about 523,000 steps with insertion sort, so the gain is large.
Counting inversions
Inversion is a pair of positions i < j where the value at i is greater than the value at j. A sorted list has 0 inversions, and a reversed list of n items has n(n-1)/2.
An inversion is a pair where a bigger value comes before a smaller one. While merging, each time a value is taken from the right half, all values still waiting in the left half are bigger and form inversions with it.
Example 5 · Brute force inversions: O(n squared)
def inversions_slow(items): count = 0 for i in range(len(items)): for j in range(i + 1, len(items)): if items[i] > items[j]: count += 1 return count
print(inversions_slow([2, 4, 1, 3, 5]))3
What this code does
- Every pair is checked once. The pairs out of order are (2, 1), (4, 1) and (4, 3).
- This is fine for small input, but a list of 100000 values has about five billion pairs.
Example 6 · Inversions with merge sort: O(n log n)
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 merged += left[i:] + right[j:] return merged, a + b + cross
print(sort_and_count([2, 4, 1, 3, 5]))print(sort_and_count([5, 4, 3, 2, 1])[1])print(sort_and_count([1, 2, 3])[1])([1, 2, 3, 4, 5], 3) 10 0
What this code does
len(left) - ivalues are still waiting in the left half, and all of them are bigger than the right value just taken.- The reversed list of 5 has 5 * 4 / 2 = 10 inversions, and a sorted list has none.
Next step
Check your understanding
11 quick questions