Lesson 24 — Merge sort

Merge sort: split in half, sort, merge

Merge sort splits the list in half, sorts each half recursively, then merges the two sorted halves (the merge from Lesson 15). It is always O(n log n), and it is stable: equal items keep their original order.

m = len(a) // 2
left, right = a[:m], a[m:]

Why it matters: Python's own sorted() uses Timsort, a merge-sort hybrid. Stability matters when you sort by one column after another.