Lesson 4 of 16

Divide, Solve, and Combine

Split a large collection into two parts, sort each part, then combine them by repeatedly taking the smaller front item. Divide and conquer follows three steps: divide, solve, combine.

Follow merge sort

Split [8, 3, 6, 1] into [8, 3] and [6, 1]. Splitting again leaves single items, already sorted. Merge them into [3, 8] and [1, 6], then combine in the order 1 → 3 → 6 → 8.

def merge_sort(values):
    if len(values) <= 1:
        return values.copy()
    mid = len(values) // 2
    left = merge_sort(values[:mid])
    right = merge_sort(values[mid:])
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

print(merge_sort([8, 3, 6, 1]))

The result is [1, 3, 6, 8]. The condition len(values) <= 1 stops subdivision. Choosing from the left on <= also preserves the original order of equal values.

Why is the cost not O(log n)?

The division depth is about log₂ n, but merging all items at each depth takes O(n) work. Total time is therefore O(n log n). Solving both halves gives the recurrence T(n) = 2T(n/2) + O(n).

Binary search continues into only one half, so T(n) = T(n/2) + O(1) gives O(log n). Both halve a range, but they process different amounts afterward.

This merge sort uses at most O(n) extra space for new lists. Quicksort partitions around a pivot before solving the parts; its cost depends on how balanced those partitions are.

Check your understanding

If the merge step takes the larger front value first, will the result still be ascending? Is correct subdivision enough?