AI Hints
Home›DSA in Python Tutorial›Better Sorts
DSA in Python · Lesson 54 of 132

Why Merge Sort Is Fast

O(n log n).

⏱ 2 min read▶ Video at 1:03:00🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

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.

Why Merge Sort Is Fast
From the video: Why Merge Sort Is Fast
  • 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.

8 itemslog₂ 8 = 3 levels
Each levelmerges all n items
Totaln × log n
1 million itemsabout 20 levels

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.

race.pypython
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")
Output
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
Next up: Quick Sort — pick a pivot