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]

[6, 3, 8, 1, 5, 2, 7, 4]
       /              \
[6, 3, 8, 1]    [5, 2, 7, 4]
   /     \         /     \
[6, 3]  [8, 1]  [5, 2]  [7, 4]
 / \     / \     / \     / \
[6] [3] [8] [1] [5] [2] [7] [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

[6] [3] [8] [1] [5] [2] [7] [4]
 \ /     \ /     \ /     \ /
[3, 6]  [1, 8]  [2, 5]  [4, 7]
   \      /         \      /
[1, 3, 6, 8]    [2, 4, 5, 7]
        \            /
  [1, 2, 3, 4, 5, 6, 7, 8]

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