Merge Sort
Sorting: lesson 5 of 8
Split until trivial, then merge your way back up.
Lesson 5 of 8 · 6 min
Merge Sort
Step 1 of 20
5
2
9
1
7
3
8
4
5
2
9
1
7
3
8
4
5
2
9
1
7
3
8
4
5
2
9
1
7
3
8
4
Merge sort does nothing clever on the way down — it just keeps splitting at the midpoint.
The Idea
Split the array in half, sort each half recursively, then merge the two sorted halves in a single pass. The splitting is log n levels deep and every level costs O(n), so you get O(n log n) every single time.
Real-World Example
Two graders each finish a stack of exam papers sorted by score. Combining them just means repeatedly taking whichever top paper is higher, one sweep through both stacks, with no re-sorting at all.
The Code
def merge_sort(nums):
if len(nums) <= 1:
return nums
mid = len(nums) // 2
left = merge_sort(nums[:mid]) # sort each half
right = merge_sort(nums[mid:])
out, i, j = [], 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]: # <= is what keeps it stable
out.append(left[i]); i += 1
else:
out.append(right[j]); j += 1
return out + left[i:] + right[j:] # drain the leftovers
# merge_sort([5, 2, 9, 1]) -> [1, 2, 5, 9]Your turn
Put the steps in the right order.
- Merge the two sorted halves into one array
- Recursively sort each half
- Split the array at the midpoint
- Return immediately if the array holds one element
Mini quiz
1 / 3