What you'll learn
Merge sort is the first algorithm to beat O(n²). It uses divide and conquer: split the array in half, sort each half, then merge the two sorted halves. The result is a rock-solid, stable O(n log n) sort.
By the end you'll be able to:
- Explain the divide-and-conquer strategy
- Perform the merge of two sorted lists with two pointers
- Derive why merge sort is
O(n log n)
Divide & conquer
Keep splitting the array in half until every piece has a single element (which is trivially sorted). Then merge pairs of sorted pieces back together, doubling the sorted-run size each level. There are log₂(n) levels of splitting, and each merge level touches all n elements:
Split down to single elements…
…then merge sorted runs back up
The merge step
Merging two already sorted lists is the heart of the algorithm. Walk a pointer along each list and repeatedly take the smaller front element — that's O(n) for the merge. Using ≤ when the fronts are equal keeps the sort stable.
Watch it sort
Here it is bottom-up: merge size-1 runs into size-2, then size-4, then the whole array:
In code
def merge_sort(a):
if len(a) <= 1:
return a
mid = len(a) // 2
left = merge_sort(a[:mid]) # divide
right = merge_sort(a[mid:])
return merge(left, right) # conquer
def merge(left, right):
out, i, j = [], 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]: # <= keeps it stable
out.append(left[i]); i += 1
else:
out.append(right[j]); j += 1
out.extend(left[i:])
out.extend(right[j:])
return outComplexity
| Measure | Value | Why |
|---|---|---|
Time (all cases) | O(n log n) | log n merge levels × O(n) work each |
Space | O(n) | Needs a temporary array to merge |
Stable? | Yes | Ties keep their original order |
Good for | Linked lists, huge/external data | Sequential access, predictable performance |
Key idea
O(n log n) holds in the worst case — unlike quick sort. Its cost is the extra O(n) memory. It also shines on linked lists, where splitting and merging need no random access.Recap & quick check
Key takeaways
- Merge sort splits in half recursively, then merges sorted halves.
- Merging two sorted lists is O(n) with a two-pointer walk.
- There are log n levels × O(n) work = O(n log n) in every case.
- It's stable but needs O(n) extra space for the merge.
- Ideal for linked lists and data too big to fit in memory.
Quick check
1. What is the time complexity of merge sort?
2. The merge step combines two lists that are:
3. Merge sort's main drawback versus quick sort is:
4. Why is merge sort a great fit for linked lists?
Merge sort is reliable but needs extra memory. Next: an in-place sorter that's usually even faster. Next up: Module 12 — Quick Sort.