Merge Sort

The Big Idea

Merge Sort is another divide-and-conquer algorithm. It works by:

1. Dividing the list into two halves.
2. Recursively sorting each half.
3. Merging the two sorted halves into a single sorted list.

The recursion is essential: instead of sorting the entire list in one go, Merge Sort keeps dividing it into smaller subproblems until they are trivial (a list of one element is already sorted).

Why Recursion Matters

• Decomposition: A big list becomes two smaller lists.
• Self-similarity: Each half is sorted with the same algorithm.
• Base case: When the list length is 1 (or 0), recursion stops.

This recursive structure makes Merge Sort clean and predictable.

Python Implementation

def merge_sort(lst):
    # Base case: lists of length 0 or 1 are already sorted
    if len(lst) <= 1:
        return lst

    # Step 1: Divide
    mid = len(lst) // 2
    left_half = lst[:mid]
    right_half = lst[mid:]

    # Step 2: Recursively sort both halves
    left_sorted = merge_sort(left_half)
    right_sorted = merge_sort(right_half)

    # Step 3: Merge the sorted halves
    return merge(left_sorted, right_sorted)


def merge(left, right):
    """Merge two sorted lists into a single sorted list."""
    merged = []
    i = j = 0

    # Compare elements and add the smaller one
    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

    # Add any remaining elements
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged


# Example use
numbers = [8, 3, 7, 4, 9, 2]
print(merge_sort(numbers))  # Output: [2, 3, 4, 7, 8, 9]

Trace Table Example

Let’s trace the call merge_sort([8, 3, 7, 4]).

Final sorted list: [3, 4, 7, 8]

Comparing to Quicksort

• Quicksort partitions around a pivot, then recurses.
• Merge Sort divides in the middle, sorts recursively, then merges.

Both rely heavily on recursion, but their combine step is different:

• Quicksort recombines via concatenation (left + pivot + right).
• Merge Sort recombines via a careful merge of two sorted halves.

IB Command Term Reminder

If the exam uses “Explain”, a strong answer should be:

“Merge Sort recursively divides a list into two halves, sorts each half, and merges them together. Recursion is essential because each sublist is itself sorted by the same algorithm until the base case of a single element is reached.”

A weak answer would be:

“Merge Sort uses recursion to sort a list.” (too vague).