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

Merge Sort

Divide and conquer.

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

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.

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

merge.pypython
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]))
Output
[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.

merge_sort.pypython
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]))
Output
[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)
Next up: Why Merge Sort Is Fast — O(n log n)