Merge Sort Algorithm

This lesson covers the merge sort algorithm as required by OCR J277 Section 2.2. Merge sort is the second standard sorting algorithm you must know for the OCR GCSE Computer Science exam. Unlike bubble sort, merge sort uses a "divide and conquer" strategy and is significantly more efficient for large datasets.

---

What Is Merge Sort?

Merge sort is a sorting algorithm that uses a divide and conquer approach. It works by:

1. Dividing the unsorted list into smaller sub-lists until each sub-list contains only one element (a list of one element is considered sorted).
2. Merging the sub-lists back together in the correct order to produce sorted sub-lists, continuing until the entire list is sorted.

---

How Merge Sort Works — The Divide Phase

The first phase splits the list repeatedly in half:

1. If the list has one element or is empty, it is already sorted — return it.
2. Find the middle of the list.
3. Split the list into two halves: left and right.
4. Recursively apply merge sort to both halves.

Example: Dividing [6, 3, 8, 1, 5, 2, 7, 4]

graph TD
  N0["[6, 3, 8, 1, 5, 2, 7, 4]"] --> N1["[6, 3, 8, 1]"]
  N0 --> N2["[5, 2, 7, 4]"]
  N1 --> N3["[6, 3]"]
  N1 --> N4["[8, 1]"]
  N2 --> N5["[5, 2]"]
  N2 --> N6["[7, 4]"]
  N3 --> N7["[6]"]
  N3 --> N8["[3]"]
  N4 --> N9["[8]"]
  N4 --> N10["[1]"]
  N5 --> N11["[5]"]
  N5 --> N12["[2]"]
  N6 --> N13["[7]"]
  N6 --> N14["[4]"]

---

How Merge Sort Works — The Merge Phase

The second phase merges the sorted sub-lists back together:

1. Compare the first elements of each sub-list.
2. Take the smaller element and add it to the merged list.
3. Repeat until all elements from both sub-lists have been merged.

Example: Merging Back Together

graph BT
  A1["[6]"] --> M1["[3, 6]"]
  A2["[3]"] --> M1
  A3["[8]"] --> M2["[1, 8]"]
  A4["[1]"] --> M2
  A5["[5]"] --> M3["[2, 5]"]
  A6["[2]"] --> M3
  A7["[7]"] --> M4["[4, 7]"]
  A8["[4]"] --> M4
  M1 --> L1["[1, 3, 6, 8]"]
  M2 --> L1
  M3 --> L2["[2, 4, 5, 7]"]
  M4 --> L2
  L1 --> R["[1, 2, 3, 4, 5, 6, 7, 8]"]
  L2 --> R

OCR Exam Tip: In exam questions, you are often asked to "show the stages of a merge sort". Make sure you show BOTH the divide phase (splitting into halves) AND the merge phase (combining in order). Showing only one phase will lose marks.

---

Merge Sort in OCR Pseudocode

function mergeSort(list)
    if list.length <= 1 then
        return list
    endif

    mid = list.length DIV 2
    left = mergeSort(list[0 to mid - 1])
    right = mergeSort(list[mid to list.length - 1])

    return merge(left, right)
endfunction

function merge(left, right)
    result = []
    while left.length > 0 AND right.length > 0
        if left[0] <= right[0] then
            result.append(left[0])
            left.remove(0)
        else
            result.append(right[0])
            right.remove(0)
        endif
    endwhile

    while left.length > 0
        result.append(left[0])
        left.remove(0)
    endwhile

    while right.length > 0
        result.append(right[0])
        right.remove(0)
    endwhile

    return result
endfunction

Merge Sort in Python

def merge_sort(lst):
    if len(lst) <= 1:
        return lst

    mid = len(lst) // 2
    left = merge_sort(lst[:mid])
    right = merge_sort(lst[mid:])

    return merge(left, right)

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:])
    result.extend(right[j:])
    return result

numbers = [6, 3, 8, 1, 5, 2, 7, 4]
print(merge_sort(numbers))  # Output: [1, 2, 3, 4, 5, 6, 7, 8]

---

Properties of Merge Sort

Property	Detail
Best case	O(n log n)
Worst case	O(n log n)
Average case	O(n log n)
Space complexity	O(n) — requires additional memory for the sub-lists
Stability	Stable — equal elements maintain their relative order
Approach	Divide and conquer using recursion

---

Key Terminology

• Divide and conquer — a problem-solving strategy that breaks a problem into smaller sub-problems, solves each one, and combines the results.
• Recursion — when a function calls itself. Merge sort is a recursive algorithm because mergeSort calls itself on the left and right halves.

---

Summary

• Merge sort splits the list in half repeatedly, then merges sorted halves back together.
• It uses a divide and conquer approach and is recursive.
• It has a consistent time complexity of O(n log n) in all cases.
• It requires additional memory (O(n)) for the temporary sub-lists.
• It is very efficient for large datasets but uses more memory than bubble sort.

OCR Exam Tip: When describing merge sort, always mention three key ideas: (1) it splits the list into halves, (2) it keeps splitting until single elements remain, and (3) it merges them back in order. These three points will typically earn full marks on a "describe" question.

---

Detailed Merge Phase Trace

The merge phase is the part students most often get wrong. Let us trace merging [3, 6] with [1, 8]:

Step	left	right	result	Explanation
Init	[3, 6]	[1, 8]	[]	Start with both pointers at index 0
1	[3, 6]	[1, 8]	[1]	Compare 3 and 1; 1 < 3, add 1 to result, advance right
2	[3, 6]	[8]	[1, 3]	Compare 3 and 8; 3 < 8, add 3 to result, advance left
3	[6]	[8]	[1, 3, 6]	Compare 6 and 8; 6 < 8, add 6 to result, advance left
4	[]	[8]	[1, 3, 6, 8]	Left is empty; append remaining right elements

Final merged list: [1, 3, 6, 8]. Notice that the merge is always linear in the size of the two lists — O(n) at each level.

---

Extended Trace: Full Merge Sort on [8, 3, 1, 7, 4, 2]

Divide phase:

graph TD
  N0["[8, 3, 1, 7, 4, 2]"] --> N1["[8, 3, 1]"]
  N0 --> N2["[7, 4, 2]"]
  N1 --> N3["[8]"]
  N1 --> N4["[3, 1]"]
  N2 --> N5["[7]"]
  N2 --> N6["[4, 2]"]
  N4 --> N7["[3]"]
  N4 --> N8["[1]"]
  N6 --> N9["[4]"]
  N6 --> N10["[2]"]

Merge phase (bottom up):