Merge Sort

Jr Codex DSA Notes

Level: Intermediate Prerequisites: Chapter 3 Time to complete: ~25 minutes

Divide and Conquer
The Merge Step
Full Implementation
Deriving O(n log n) Informally
Space Cost
Stability
Summary & Next Steps

1. Divide and Conquer

Merge sort splits the array in half recursively until each piece has one element (trivially sorted), then merges pieces back together in sorted order. This "split, solve small pieces, combine" strategy is called divide and conquer — you'll see the same shape again in quick sort (Chapter 5) and several graph/DP algorithms later in this curriculum.

[5, 2, 8, 1]
    ↓ split
[5, 2]        [8, 1]
    ↓ split       ↓ split
[5] [2]       [8] [1]
    ↓ merge       ↓ merge
[2, 5]        [1, 8]
    ↓─────── merge ───────↓
      [1, 2, 5, 8]

2. The Merge Step

Given two already-sorted lists, merging them into one sorted list takes one linear pass, comparing the fronts of each:

def merge(left, right):
    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:])     # append any leftovers
    result.extend(right[j:])
    return result
    # O(n) time where n = len(left) + len(right)

This is the same "opposite-direction two-pointer" shape from Module 2, Chapter 3 — just walking two separate lists instead of two ends of one list.

3. Full Implementation

def merge_sort(items):
    if len(items) <= 1:
        return items                       # base case: a single element is sorted
 
    mid = len(items) // 2
    left = merge_sort(items[:mid])          # recursively sort left half
    right = merge_sort(items[mid:])          # recursively sort right half
 
    return merge(left, right)                 # combine the two sorted halves

4. Deriving O(n log n) Informally

Two facts combine to give the total complexity:

The array is halved at each level of recursion → log n levels total, just like binary search (Chapter 1) and the O(log n) examples in Module 1.
Merging all the pieces back together at any one level costs O(n) total — even though there are many small merges at a given level, together they touch every element exactly once.

Level 0:  [8 elements]                     → 1 merge of size 8   → O(n)
Level 1:  [4] [4]                          → 2 merges of size 4  → O(n) total
Level 2:  [2][2] [2][2]                    → 4 merges of size 2  → O(n) total
Level 3:  [1][1][1][1] [1][1][1][1]        → base case, no merge needed

log₂(8) = 3 levels of merging × O(n) work per level = O(n log n)

5. Space Cost

Unlike the in-place sorts from Chapters 2-3, merge sort allocates new lists at every merge step — its auxiliary space is O(n) (Module 1, Chapter 4). This is the direct tradeoff for guaranteeing O(n log n) in every case, including the worst case — unlike quick sort (Chapter 5), which is in-place but can degrade to O(n²).

6. Stability

Merge sort is stable, provided the merge step uses <= (not <) when comparing — as written above, when left[i] equals right[j], the element from left is taken first, preserving original order for equal elements. This is a key reason merge sort (or a hybrid built on it, like Python's Timsort) is preferred whenever stability is required — e.g., sorting by one field while preserving order on ties.

7. Summary & Next Steps

Key Takeaways

Merge sort is a divide-and-conquer algorithm: split recursively to single elements, then merge back together in sorted order.
Its O(n log n) complexity comes from log n levels of splitting, each doing O(n) total work to merge.
It requires O(n) auxiliary space — the tradeoff for guaranteeing O(n log n) even in the worst case.
It's stable, provided the merge step breaks ties in favor of the left half.

Concept Check

Why does merge sort's recursion have log n levels?
Why is the total merging work at any one level O(n), even though there are multiple separate merge calls at that level?
Why does merge sort need O(n) extra space, unlike bubble/selection/insertion sort?

Next Chapter

→ Chapter 5: Quick Sort

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index