Merge Sort

Prev Next

Merge sort is the first genuinely divide-and-conquer algorithm in this track: instead of fixing the list one comparison at a time, it splits the problem into smaller pieces, solves those pieces recursively, and then does the real work combining the answers back together. It guarantees O(n log n) time in every case — best, average, and worst alike — which is exactly why it's the backbone half of Python's own Timsort, as the previous lesson foreshadowed.

Divide and Conquer, In Words

Split the list in half. Recursively sort each half. Merge the two now-sorted halves back into one sorted whole. The recursion bottoms out at lists of length 0 or 1, which are trivially already sorted. All the actual sorting work happens in the merge step — the splitting itself does nothing but divide indices.

def merge_sort(items):
    if len(items) <= 1:
        return items                      # base case: 0 or 1 element is already sorted

    mid = len(items) // 2
    left = merge_sort(items[:mid])       # recursively sort the left half
    right = merge_sort(items[mid:])      # recursively sort the right half

    return merge(left, right)             # combine the two sorted halves

Time complexity: O(n log n) overall — derived fully below. Space complexity: O(n) — every recursive call slices new sub-lists and the merge step below builds a new combined list, none of it done in place.

The merge() Helper, Fully Worked

Given two already-sorted lists, merge them into one sorted list by repeatedly comparing their fronts and taking the smaller one. Because each input list is already sorted, the smallest remaining candidate overall is always sitting at the front of one list or the other — you never need to look any deeper than that.

def merge(left, right):
    result = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] <= right[j]:            # <= (not <) keeps left's element first on ties -- stability
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    result.extend(left[i:])              # copy over whatever is left in `left` (if any)
    result.extend(right[j:])             # copy over whatever is left in `right` (if any)
    return result


print(merge([1, 4, 7], [2, 3, 9]))   # [1, 2, 3, 4, 7, 9]

Trace merging [1, 4, 7] and [2, 3, 9]: compare 1 vs 2 → take 1. Compare 4 vs 2 → take 2. Compare 4 vs 3 → take 3. Compare 4 vs 9 → take 4. Compare 7 vs 9 → take 7. Left is now exhausted, so the remaining right elements ([9]) are copied over wholesale. Result: [1, 2, 3, 4, 7, 9].

Time complexity: O(n) where n is the combined length of both lists — each element from both lists is examined and appended exactly once. Space complexity: O(n) — the result list holds a full new copy of every element from both inputs.

The Recursion Tree, Visualized

Sorting [8, 3, 5, 1, 9, 2, 7, 4] (8 elements) splits repeatedly until every piece has 1 element, then merges back up level by level:

Level 0 (split): [8,3,5,1,9,2,7,4]
Level 1 (split): [8,3,5,1]            [9,2,7,4]
Level 2 (split): [8,3]     [5,1]      [9,2]     [7,4]
Level 3 (split): [8][3]    [5][1]     [9][2]    [7][4]   <- base case, length 1

Level 3 (merge): [3,8]     [1,5]      [2,9]     [4,7]
Level 2 (merge): [1,3,5,8]            [2,4,7,9]
Level 1 (merge): [1,2,3,4,5,7,8,9]

3 split levels for n=8 (log2(8) = 3), each merge level touches
all 8 elements once -> 3 levels x O(n) work per level = O(n log n).
          

Level	Number of sub-lists	Work per level
0 (whole list)	1	O(n) merge work at this level
1	2	O(n) total — two merges of n/2 elements each
...	...	always O(n) total per level
log₂(n) (base case)	n	O(n) — n single-element lists, trivially sorted

Deriving O(n log n) Time and O(n) Space

The recursion halves the list at every level, so it takes log₂(n) levels to reach single-element base cases (exactly matching binary search's halving logic, applied to splitting instead of searching). Crucially, no matter how many pieces a level is split into, the merge work across an entire level always adds up to O(n) total — merging two lists of combined size k costs O(k), and all the sub-list sizes at one level always sum to n. Multiply: log₂(n) levels × O(n) work per level = O(n log n) overall.

Space is O(n) rather than O(1) because, unlike the in-place O(n²) sorts from the previous lesson, merge sort's merge() step builds a brand-new result list at every merge call — Python's slicing (items[:mid]) also creates new lists rather than views. The recursion stack itself only adds O(log n), but the O(n) auxiliary space for merged output dominates.

Time complexity: O(n log n) — same in the best, average, and worst case, since the split points never depend on the data's order. Space complexity: O(n) — auxiliary space for the merged results at every level, dominating the O(log n) recursion stack depth.

Stability

Merge sort is stable — and the reason is visible directly in the code above: the comparison in merge() uses <=, not <, so when left[i] and right[j] are equal, the element from left is always taken first. Since left came from an earlier position in the original list, this preserves the original relative order of equal elements.

The Timsort connection: Python's built-in sorted() and list.sort() use Timsort, which finds or creates small sorted "runs" (using insertion sort, from the previous lesson) and then merges those runs together using precisely this merge logic — adaptive run-finding on top of the same merge idea you just implemented by hand.

Next up: Quick Sort is also divide-and-conquer, but it partitions around a pivot instead of merging — trading merge sort's guaranteed O(n log n) for an in-place algorithm that's usually faster in practice.

Prev Next