Why Merge Sort Is Fast
O(n log n).
Merge sort is O of N log N. Where does that come from? Picture the splitting as levels. Each level does O of N work merging, and there are only log N levels, because we halve the list each time.

- O(n log n)
- Each level: O(n) merging
- log n levels
Levels of splitting
Eight items split into two halves of four, then four pieces of two, then eight pieces of one. That's three levels, and log two of eight is three. At every level, merging touches all eight items once. So the total is eight times three. In general, N times log N.
Race: bubble versus merge
Let's race them, on five thousand random numbers. Run it. Merge sort finishes in a tiny fraction of the time. And Python's built in sort is faster still, because it's written in C, and uses an even cleverer algorithm.
import random, time
from sorts import bubble_sort, merge_sort
data = [random.randint(0, 10_000) for _ in range(5_000)]
for name, fn in [("bubble", bubble_sort), ("merge", merge_sort), ("sorted", sorted)]:
start = time.perf_counter()
fn(list(data))
print(f"{name:<7} {time.perf_counter() - start:.4f} s")bubble 1.0014 s merge 0.0073 s sorted 0.0004 s
Also uses sorts.py
def bubble_sort(nums):
n = len(nums)
for i in range(n - 1):
for j in range(n - 1 - i):
if nums[j] > nums[j + 1]:
nums[j], nums[j + 1] = nums[j + 1], nums[j]
return nums
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:]
def merge_sort(nums):
if len(nums) <= 1:
return nums
mid = len(nums) // 2
return merge(merge_sort(nums[:mid]), merge_sort(nums[mid:]))Summary
Merge sort is O of N log N, because there are log N levels, and each does O of N work. That's the best possible for sorting by comparing. Next, another fast sort. Quick sort.
Key takeaways- log n levels
- O(n) per level
- O(n log n) total