Merge Sort and Divide-and-Conquer

Sorting a Thousand Papers

It's exam season. You're a professor with 1000 student papers on your desk, and you need them sorted alphabetically by last name.

You could sort them yourself — scanning through the pile, picking the next in order — but that would take hours. Instead, you try a different approach:

You split the pile in half. You give 500 papers to your teaching assistant Alice, and 500 to your teaching assistant Bob. You tell them each to sort their pile. An hour later, both return with sorted stacks.

Now you have two sorted piles. Merging them is easy: compare the top paper of each stack, pick the smaller one (alphabetically earlier), set it aside. Repeat until both stacks are empty. In minutes, you have one fully sorted stack of 1000 papers.

This is Merge Sort. The insight: sorting two halves separately and merging is much faster than sorting the whole directly.

The Divide-and-Conquer Paradigm

Merge sort is the canonical example of divide and conquer — a three-step strategy that appears throughout computer science:

1. DIVIDE   — Split the problem into smaller subproblems
2. CONQUER  — Solve each subproblem recursively
3. COMBINE  — Merge the solutions into the final answer

The power of divide and conquer: if you can split a problem of size n into two problems of size n/2, and merging takes O(n) work, then the total work is O(n log n) — far better than O(n²).

Merge Sort Recursion Tree

Let's sort [38, 27, 43, 3, 9, 82, 10]:

The tree has log₂(n) levels. Each level does O(n) total work (merging). Total: O(n log n).

The Merge Step — The Heart of the Algorithm

The merge function takes two sorted arrays and produces one sorted array. It works by always picking the smaller of the two front elements:

Complete Implementation

def merge_sort(arr):
    # Base case: arrays of 0 or 1 element are already sorted
    if len(arr) <= 1:
        return arr

    # DIVIDE: split into two halves
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])   # recursively sort left half
    right = merge_sort(arr[mid:])  # recursively sort right half

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


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

    # Compare front elements of each half, pick the smaller
    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

    # Append any remaining elements (one side exhausted first)
    result.extend(left[i:])    # remaining left elements (already sorted)
    result.extend(right[j:])   # remaining right elements (already sorted)

    return result


# Test
arr = [38, 27, 43, 3, 9, 82, 10]
print("Input: ", arr)
sorted_arr = merge_sort(arr)
print("Output:", sorted_arr)

Output:

Input:  [38, 27, 43, 3, 9, 82, 10]
Output: [3, 9, 10, 27, 38, 43, 82]

Traced execution (simplified):

merge_sort([38,27,43,3,9,82,10])
  merge_sort([38,27,43,3])
    merge_sort([38,27])
      merge_sort([38]) → [38]
      merge_sort([27]) → [27]
      merge([38],[27]) → [27,38]
    merge_sort([43,3])
      merge_sort([43]) → [43]
      merge_sort([3])  → [3]
      merge([43],[3])  → [3,43]
    merge([27,38],[3,43]) → [3,27,38,43]
  merge_sort([9,82,10])
    merge_sort([9,82])
      merge([9],[82])  → [9,82]
    merge_sort([10])   → [10]
    merge([9,82],[10]) → [9,10,82]
  merge([3,27,38,43],[9,10,82]) → [3,9,10,27,38,43,82]

Complexity Analysis

Why always O(n log n)?

• The recursion tree always has exactly log₂(n) levels (we always halve)
• Each level does exactly n total comparisons (in the merge step)
• log₂(n) levels × n work per level = O(n log n) — regardless of input order

This guaranteed O(n log n) is merge sort's killer feature. Unlike quicksort, there's no bad input that degrades performance.

Space: O(n) — the merge step creates a new result array. This is merge sort's main weakness compared to in-place algorithms.

Why Merge Sort Is Used for External Sorting

External sorting means sorting data that doesn't fit in RAM — terabytes on disk.

Consider sorting a 1TB log file with only 16GB of RAM:

1. Read 16GB chunks into RAM, merge sort each chunk, write sorted chunks back to disk
2. Now you have many sorted files on disk
3. Use merge sort's merge step to combine sorted files, reading small buffers at a time

Merge sort is ideal for this because:

• It accesses data sequentially — ideal for disk reads (random access on HDDs is slow)
• The merge step only needs one element from each sorted subarray at a time
• It's naturally parallelizable — each half can be sorted independently

This is why database engines and distributed systems (like Hadoop's sort phase in MapReduce) use merge sort at their core.

Stability: Merge Sort Preserves Relative Order

Merge sort is a stable sorting algorithm.

Stable means: if two elements are equal, the one that appeared first in the input also appears first in the output.

Why stability matters — sorting a list of students by grade:

Input: [(Alice, B), (Bob, A), (Charlie, B), (Diana, A)]

Stable sort by grade:
  Output: [(Bob, A), (Diana, A), (Alice, B), (Charlie, B)]
  Bob comes before Diana (original order preserved for A's)
  Alice comes before Charlie (original order preserved for B's)

Unstable sort might give:
  Output: [(Diana, A), (Bob, A), (Charlie, B), (Alice, B)]
  Order within equal elements is arbitrary

Stability enables multi-key sorting: sort by grade first (stable), then sort by name — the grade order within each name group is preserved.

Merge Sort vs. The Alternatives

Key Takeaways

• Merge sort follows the divide-and-conquer strategy: split, solve recursively, merge
• The recursion tree has log₂(n) levels, each level does O(n) work → O(n log n) total
• Guaranteed O(n log n) in all cases — no bad input can make it worse
• Space complexity is O(n) — requires auxiliary array for merging
• Stable — equal elements maintain their relative order
• The algorithm of choice for external sorting (data larger than RAM)
• Used in production: Python's Timsort uses merge for the combining phase, Java's Arrays.sort() for objects

Next lesson: Quicksort — faster in practice, but with a dramatic worst-case twist.