Every algorithm in the previous lesson does roughly $n^2$ comparisons in the worst case. Merge sort breaks that ceiling with one idea: split the problem in half, solve each half, then spend a single linear pass merging the two sorted halves back together. That’s divide and conquer, and it’s the same pattern behind binary search, quicksort, and a huge share of efficient algorithms you’ll meet later.

What you’ll learn

• The merge step — combining two already-sorted lists into one sorted list in a single $O(n)$ pass.
• The recursive split — dividing the array in half until pieces are trivially sorted (size 0 or 1).
• Why the recurrence $T(n) = 2T(n/2) + O(n)$ solves to $O(n \log n)$.
• Why merge sort is stable and needs $O(n)$ extra space — unlike the in-place $O(n^2)$ sorts from the last lesson.
• Where Python’s own sorted()sorted() fits into this story.

The merge step: combine two sorted lists in one pass

If you already have two sorted lists, you never need to look backward to merge them: walk both with a pointer, always take the smaller of the two current fronts, and advance that pointer. When one list runs out, the rest of the other list is already in order — just copy it over.

def merge(left, right):
    merged = []
    i = j = 0
 
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
 
    merged.extend(left[i:])    # copy whatever's left, if anything
    merged.extend(right[j:])
    return merged
 
 
left = [1, 4, 7]
right = [2, 3, 9]
print(merge(left, right))   # expect [1, 2, 3, 4, 7, 9]

def merge(left, right):
    merged = []
    i = j = 0
 
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
 
    merged.extend(left[i:])    # copy whatever's left, if anything
    merged.extend(right[j:])
    return merged
 
 
left = [1, 4, 7]
right = [2, 3, 9]
print(merge(left, right))   # expect [1, 2, 3, 4, 7, 9]

Every element is looked at exactly once, so mergemerge runs in $O(n)$ time where $n$ is the combined length of both lists — this is the linear “combine” step that makes the whole algorithm work.

The recursive split

Merge only helps if you already have two sorted halves. Merge sort gets those halves the same way it got the whole array sorted: recursively. Split the array in half, sort each half (recursively), then merge the results. The recursion bottoms out at size 0 or 1 — a list of one element is trivially already sorted.

def merge(left, right):
    merged = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged
 
 
def merge_sort(arr):
    if len(arr) <= 1:          # base case: already sorted
        return arr
 
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)
 
 
nums = [8, 3, 5, 1, 9, 2]
print(merge_sort(nums))   # expect [1, 2, 3, 5, 8, 9]

def merge(left, right):
    merged = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged
 
 
def merge_sort(arr):
    if len(arr) <= 1:          # base case: already sorted
        return arr
 
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)
 
 
nums = [8, 3, 5, 1, 9, 2]
print(merge_sort(nums))   # expect [1, 2, 3, 5, 8, 9]

The recursion builds a tree $\log_2 n$ levels deep — each level does a total of $O(n)$ merge work across all its calls, since every element is touched exactly once per level:

  graph TD
    N0["[8, 3, 5, 1]"] --> N1["[8, 3]"]
    N0 --> N2["[5, 1]"]
    N1 --> N3["[8]"]
    N1 --> N4["[3]"]
    N2 --> N5["[5]"]
    N2 --> N6["[1]"]

Splitting stops at single elements (the base case), and then merging climbs back up: [8][8] and [3][3] merge into [3, 8][3, 8]; [5][5] and [1][1] merge into [1, 5][1, 5]; finally [3, 8][3, 8] and [1, 5][1, 5] merge into [1, 3, 5, 8][1, 3, 5, 8].

Why this is O(n log n)

Every recursive call splits the array in half and does $O(n)$ work in the merge step to recombine the results. That’s exactly the shape of recurrence covered in Recurrences and the Master Theorem:

There are $\log_2 n$ levels of recursion (each halving shrinks $n$ down to 1 after $\log_2 n$ steps), and every level does $O(n)$ total merge work across all the calls at that depth. Multiply the two together:

Unlike bubble, selection, and insertion sort, this bound holds in the best, average, and worst case — merge sort never degrades, because the split is always exactly in half regardless of the input’s order.

Time and space complexity

LeetCode problem set

Practice — real LeetCode problems

Each exercise is the actual LeetCode problem with its real method signature and LeetCode’s own examples as the test. Write the body, press Run, and match the expected output.

LC 88 — Merge Sorted Array · Easy

Problem. nums1nums1 has length m + nm + n, with its first mm slots holding sorted values and the rest set to 00. Merge the nn sorted values of nums2nums2 into nums1nums1 in place.

Constraints. 0 <= m, n <= 2000 <= m, n <= 200, both inputs sorted non-decreasing.

Examples. nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 gives [1,2,2,3,5,6][1,2,2,3,5,6]

LC 977 — Squares of a Sorted Array · Easy

Problem. Given an array sorted in non-decreasing order, return an array of the squares of each number, also sorted non-decreasing. Aim for $O(n)$.

Constraints. 1 <= len(nums) <= 10^41 <= len(nums) <= 10^4, -10^4 <= nums[i] <= 10^4-10^4 <= nums[i] <= 10^4, sorted.

Examples. [-4,-1,0,3,10][-4,-1,0,3,10] gives [0,1,9,16,100][0,1,9,16,100] · [-7,-3,2,3,11][-7,-3,2,3,11] gives [4,9,9,49,121][4,9,9,49,121]

LC 148 — Sort List · Medium

Problem. Sort a linked list in $O(n \log n)$ time and, ideally, $O(1)$ extra space.

Constraints. 0 <= number of nodes <= 5 * 10^40 <= number of nodes <= 5 * 10^4, -10^5 <= Node.val <= 10^5-10^5 <= Node.val <= 10^5.

Examples. [4,2,1,3][4,2,1,3] gives [1,2,3,4][1,2,3,4] · [-1,5,3,4,0][-1,5,3,4,0] gives [-1,0,3,4,5][-1,0,3,4,5] · [][] gives [][]

Recap

• Merge combines two sorted lists in one $O(n)$ pass by always taking the smaller current front.
• Merge sort recursively splits in half down to single elements, then merges back up — the recurrence $T(n) = 2T(n/2) + O(n)$ solves to $O(n \log n)$.
• It’s stable ($O(n)$ time, guaranteed, in every case) but needs $O(n)$ extra space — unlike the $O(1)$ in-place sorts from the previous lesson.
• Python’s sorted()sorted() uses Timsort, a hybrid built on these same ideas plus insertion sort for small runs — covered in a later lesson.

Next: Quick Sort — another divide-and-conquer sort, in-place this time, with an average case just as fast but a worst case that depends entirely on how you pick the pivot.