Merge Sort
Divide and conquer.
Merge sort uses a powerful idea called divide and conquer. Split the list in half. Sort each half. Then merge the two sorted halves together. And how do you sort each half? The same way. Split, sort, and merge. That's recursion.

- Split in half
- Sort each half
- Merge them together
Merging two sorted lists
Merging is the heart of it. Two sorted lists each have a pointer at the front. We compare the two front items, and take the smaller one. When one list runs out, we add whatever's left of the other. Run it. Merging is O of N, because each item is taken exactly once.
def merge(a, b):
result, i, j = [], 0, 0
while i < len(a) and j < len(b):
if a[i] <= b[j]:
result.append(a[i]); i += 1
else:
result.append(b[j]); j += 1
return result + a[i:] + b[j:]
print(merge([1, 4, 9], [2, 3, 10, 12]))[1, 2, 3, 4, 9, 10, 12]
The full merge sort
Now the whole algorithm. A list of zero or one items is already sorted. That's the base case. Otherwise, we split at the middle, merge sort each half with recursion, and merge the results. Run it.
from merge import merge
def merge_sort(nums):
if len(nums) <= 1:
return nums
mid = len(nums) // 2
left = merge_sort(nums[:mid])
right = merge_sort(nums[mid:])
return merge(left, right)
print(merge_sort([38, 27, 43, 3, 9, 82, 10]))[3, 9, 10, 27, 38, 43, 82]
Also uses merge.py
def merge(a, b):
result, i, j = [], 0, 0
while i < len(a) and j < len(b):
if a[i] <= b[j]:
result.append(a[i]); i += 1
else:
result.append(b[j]); j += 1
return result + a[i:] + b[j:]Summary
Merge sort splits the list, sorts each half recursively, and merges them. Next, why that makes it so much faster than bubble sort.
Key takeaways- Split in half
- Recurse on each half
- Merge in O(n)