OCR J277 · Component 2 · Topic 2.1.3d

Sorting Algorithms
Merge Sort

Divide · Conquer · Merge · O(n log n)

CSZone OCR GCSE Computer Science J277

Learning Objectives

By the end of this video you will be able to...

Describe how merge sort works — including the two phases: the split phase (dividing until single elements), and the merge phase (combining sorted sub-lists in order)

Apply merge sort to a data set — draw the full split-and-merge tree, showing every sub-list at each level and each merge step in order

Trace the merge step in detail — show how two sorted sub-lists are combined element by element, comparing first elements and taking the smaller each time

Identify merge sort from given code — recognise the three signatures: divide at midpoint, recursive calls, and the compare-and-merge step with remaining elements appended

State and compare the efficiency of merge sort — O(n log n) for all cases — and explain why it outperforms bubble sort on large datasets, and when each is more appropriate

⚡ The OCR J277 spec does NOT require you to memorise or write the recursive merge sort code from memory — focus on applying and identifying the algorithm.

Merge Sort — The Concept

Divide and conquer

DEFINITION

Merge sort is a divide and conquer algorithm. It works by splitting the list in half repeatedly until every sub-list contains just one element — then merging those sub-lists back together in sorted order. The sorting happens during the merge phase, not the split phase.

NO PREREQUISITE

Merge sort works on any data — sorted, unsorted, or partially sorted. No pre-processing needed, same as bubble sort.

THE TWO PHASES

PHASE 1 — SPLIT

Divide the list into two halves. Divide each half again. Keep dividing until every sub-list has just one element. A list of one element is always sorted — this is the base case.

PHASE 2 — MERGE

Compare the first element of each sub-list. Take the smaller one into the result. Repeat until one sub-list is empty, then add all remaining elements. The result is a sorted list. Merge pairs together, working back up to the full list.

WHY IS IT FASTER THAN BUBBLE SORT?

Bubble sort compares every element with every other element — O(n²). Merge sort halves the problem with every split. Even on 1,000,000 elements, the split phase only has 20 levels. The merge phase is also efficient: each merge step is linear. Together: O(n log n) — dramatically faster.

INTUITION — SPLITTING KEEPS WORK SMALL

1 list of 8 elements
→ 2 lists of 4 · → 4 lists of 2 · → 8 lists of 1
Then merge: 4 pairs → 2 groups → 1 sorted list

At each level, every element is only involved in one merge. So each level takes O(n) work, and there are only log₂(n) levels. Total: O(n log n).

⚡ Bubble sort: O(n²). Merge sort: O(n log n). For 1,000 elements: bubble sort needs up to 500,000 comparisons; merge sort needs roughly 10,000. The difference grows rapidly with list size.

The Algorithm

Merge sort — step by step

PHASE 1 — SPLIT STEPS

1.

Find the midpoint: mid = LEN(list) DIV 2

2.

Split into two halves: left = list[0 to mid−1], right = list[mid to end]

3.

Repeat for each half. Keep splitting until every sub-list has length 1.

Base case: a list of 0 or 1 elements is already sorted. Stop splitting.

PHASE 2 — MERGE STEPS

4.

Take two sorted sub-lists. Compare their first elements.

5.

Add the smaller element to the result list. Remove it from its sub-list.

6.

Repeat steps 4–5 until one sub-list is empty.

7.

Append all remaining elements from the non-empty sub-list to the result.

THE BIG PICTURE

Merge sort is recursive — the mergeSort function calls itself on smaller and smaller sub-lists until each has one element, then the results flow back up. You don't need to write the recursive code from memory, but understanding the recursive structure helps you trace the algorithm.

KEY RULE FOR MERGING

You can only merge two already-sorted sub-lists. Single elements are always sorted. Two sorted lists always merge into one sorted list. This is why splitting to single elements first is essential.

For a list of n elements: the split phase produces log₂(n) levels. At each level, n total elements are merged. Total work: n × log₂(n) comparisons — which is O(n log n).

⚡ Exam: "What is the base case for merge sort?" Answer: a list containing zero or one element — it is already sorted and requires no further splitting.

Pseudocode & Identification

Merge sort pseudocode — for identification

PSEUDOCODE — FOR RECOGNITION ONLY (NOT REQUIRED FROM MEMORY)

FUNCTION mergeSort(data) IF LEN(data) <= 1 THEN RETURN data ← base case END IF mid = LEN(data) DIV 2 left = mergeSort(data[0:mid]) ← ① right = mergeSort(data[mid:LEN]) ← ① RETURN merge(left, right) ← ② END FUNCTION FUNCTION merge(left, right) result = [] WHILE LEN(left)>0 AND LEN(right)>0 IF left[0] <= right[0] THEN ← ③ result += left[0] left = left[1:] ELSE result += right[0] right = right[1:] END IF END WHILE RETURN result + left + right ← ④ END FUNCTION

FOUR IDENTIFICATION SIGNATURES

① RECURSIVE SELF-CALLS

The function calls itself — mergeSort(left) and mergeSort(right). Bubble sort and insertion sort don't do this.

② SPLIT AT MIDPOINT

mid = LEN DIV 2 and slicing into two halves. The function calls merge on the two recursively-sorted halves.

③ COMPARE-AND-TAKE FROM FRONT

In the merge function: compare left[0] with right[0] — always the first (smallest) element of each sub-list.

④ APPEND REMAINING ELEMENTS

result + left + right at the end — whichever sub-list isn't empty gets appended wholesale.

⚡ "Name the algorithm in this code." — The clearest identifier is the recursive self-call combined with splitting into two halves. If you see a function calling itself with left and right halves of a list, it's merge sort.

Applying Merge Sort

Full worked example — [6, 3, 8, 2]

PHASE 1 — SPLIT (top-down)

■ splitting■ base case (len=1)

Split trace:
[6,3,8,2] → mid = 4 DIV 2 = 2 → [6,3] | [8,2]
[6,3] → mid = 2 DIV 2 = 1 → [6] | [3]
[8,2] → mid = 2 DIV 2 = 1 → [8] | [2]
All sub-lists now have length 1 — base case reached.

PHASE 2 — MERGE (bottom-up)

■ base sub-lists■ merged results

⚡ In the exam, you must draw or describe both phases. The split tree works top-down; the merge tree works bottom-up. Each merge takes two sorted sub-lists and produces one sorted list.

The Merge Step

How merging works — element by element

Merging [3, 6] and [2, 8] into a single sorted list · ■ comparing ■ taken into result ■ exhausted

STEP 1 — COMPARE FIRST ELEMENTS

LEFT

3

6

vs

2

8

3 vs 2

TAKE 2 2 < 3 → take 2 from RIGHT

RESULT

2

Remaining: [3,6] and [8]

STEP 2 — COMPARE AGAIN

LEFT

3

6

vs

8

3 vs 8

TAKE 3 3 < 8 → take 3 from LEFT

RESULT

2

3

Remaining: [6] and [8]

STEP 3 — COMPARE AGAIN

LEFT

6

vs

8

6 vs 8

TAKE 6 6 < 8 → take 6 from LEFT. Left now empty.

RESULT

2

3

6

Remaining: [] and [8]

STEP 4 — APPEND REMAINING

LEFT empty [] → append all of right to result

RESULT

2

3

6

8

MERGED: [2, 3, 6, 8] ✓
Total comparisons in this merge: 3.
When one sub-list empties, add all remaining elements from the other — no more comparisons needed.

KEY RULE — WHY APPEND REMAINING?

Both sub-lists were already sorted. Once the left is empty, every element remaining in the right is guaranteed to be larger than everything already in the result. No comparison needed — just append.

⚡ Exam: "Describe the merge step." Answer: compare the first elements of the two sorted sub-lists. Take the smaller into the result and remove it from its sub-list. Repeat until one sub-list is empty, then append all remaining elements from the other sub-list.

Trace Diagram

Exam-style trace — [4, 7, 1, 5]

SPLIT PHASE

MERGE PHASE — FIRST MERGES

Merge [4] + [7]: compare 4 and 7. 4 < 7 → take 4. Right empty → append 7.
Result: [4, 7]

Merge [1] + [5]: compare 1 and 5. 1 < 5 → take 1. Right empty → append 5.
Result: [1, 5]

MERGE PHASE — FINAL MERGE [4,7] + [1,5]

Compare 4 and 1: 1 < 4 → take 1. Result: [1]. Left: [4,7] Right: [5]
Compare 4 and 5: 4 < 5 → take 4. Result: [1,4]. Left: [7] Right: [5]
Compare 7 and 5: 5 < 7 → take 5. Result: [1,4,5]. Left: [7] Right: [ ]
Right empty → append 7. Result: [1, 4, 5, 7] ✓

⚡ "How many comparisons in the final merge?" — 3 (not 4). Once the right sub-list empties after taking 5, the remaining [7] is appended without a comparison. Never count the append step as a comparison.

Efficiency

Efficiency — merge sort

MERGE SORT EFFICIENCY

BEST

O(n log n)

Even on already-sorted data, merge sort still splits and merges — no early exit like optimised bubble sort. Best case is the same as worst.

AVERAGE

O(n log n)

All cases are the same. The split phase always produces log₂(n) levels. The merge phase always processes n elements per level.

WORST

O(n log n)

Even reverse-sorted data is handled in O(n log n). No scenario makes merge sort degrade to O(n²). This consistency is a key advantage.

⚡ For 1,000,000 elements: bubble sort worst case ≈ 500 billion comparisons. Merge sort ≈ 20 million. Merge sort is about 25,000× faster in the worst case. This is why O(n log n) sorts are used in practice.

COMPARISON TABLE

	BUBBLE SORT	MERGE SORT
Best case	O(n)*	O(n log n)
Average case	O(n²)	O(n log n)
Worst case	O(n²)	O(n log n)
Memory	In-place	Extra space needed
Simplicity	Simple	More complex
Large data	Very slow	Fast

* Bubble sort best case O(n) only with swapped flag + already-sorted data

Use merge sort when data is large and efficiency matters.

Use bubble sort when data is small or nearly sorted, or simplicity matters.

Merge sort trade-off: requires additional memory to store the sub-lists during merging. Bubble sort is in-place — it only needs the original array.

Identify from Code

Identifying merge sort from given code

EXAM QUESTION STYLE — "NAME THIS ALGORITHM"

FUNCTION sort(arr) IF LEN(arr) <= 1 THEN RETURN arr END IF centre = LEN(arr) DIV 2 ← ① lo = sort(arr[0:centre]) ← ② self-call hi = sort(arr[centre:LEN]) ← ② self-call RETURN combine(lo, hi) FUNCTION combine(a, b) out = [] WHILE LEN(a)>0 AND LEN(b)>0 IF a[0] <= b[0] THEN ← ③ out += a[0] a = a[1:] ELSE out += b[0] b = b[1:] END IF END WHILE RETURN out + a + b ← ④

WHAT TO LOOK FOR — 4 SIGNATURES

① HALVING — mid / centre / DIV 2

A line finding the midpoint with DIV 2. Used to split the list — not to search (unlike binary search, which uses it as the comparison target).

② SELF-CALLS ON BOTH HALVES

Two recursive calls — one for left half, one for right half. Binary search only has ONE search space at a time. Merge sort processes BOTH halves.

③ COMPARE FIRST ELEMENTS a[0] vs b[0]

The merge function always compares index [0] of each list — always the smallest remaining element. This is the core of the merge step.

④ RETURN out + a + b (APPEND REMAINING)

After the WHILE loop, one list may still have elements. They are appended to the result without further comparison.

⚡ Renamed: sort/combine instead of mergeSort/merge, and lo/hi/centre/out instead of left/right/mid/result. Same structure. "Name this algorithm: merge sort. Justify: the function calls itself on two halves of the list and combines the results using a compare-and-take merge step."

Exam Practice

Merge sort — applying the algorithm

Question 1 — 4 marks

Apply merge sort to the list below. Draw the full split and merge tree, showing every sub-list at each stage.

List: [5, 1, 4, 2]

Answer — Q1

Split: [5,1,4,2] → [5,1] | [4,2] → [5] | [1] | [4] | [2]
First merges:
Merge [5]+[1]: 1<5 → take 1, append 5 → [1,5]
Merge [4]+[2]: 2<4 → take 2, append 4 → [2,4]
Final merge [1,5]+[2,4]:
1 vs 2 → take 1. 5 vs 2 → take 2. 5 vs 4 → take 4. Append 5.
Result: [1, 2, 4, 5] ✓

Question 2 — 3 marks

Two sorted sub-lists are to be merged: [2, 6, 9] and [3, 5, 8].
Show each step of the merge, stating which element is taken at each comparison. How many comparisons are made in total?

Answer — Q2

2 vs 3 → take 2. Result: [2]
6 vs 3 → take 3. Result: [2,3]
6 vs 5 → take 5. Result: [2,3,5]
6 vs 8 → take 6. Result: [2,3,5,6]
9 vs 8 → take 8. Result: [2,3,5,6,8]
Right empty → append 9. Final: [2,3,5,6,8,9] ✓
Comparisons: 5 (not 6 — appending 9 has no comparison)

Question 3 — 4 marks

The code below shows a sorting algorithm.
(a) Name the algorithm.
(b) Give two features that led to your identification.
(c) Give one advantage and one disadvantage of this algorithm compared to bubble sort.

FUNCTION srt(lst)
  IF LEN(lst)<=1 THEN RETURN lst
  m = LEN(lst) DIV 2
  L = srt(lst[0:m])
  R = srt(lst[m:LEN(lst)])
  RETURN join(L, R)
END FUNCTION

Exam Practice — Answers

Question 3 answered + common mistakes

Q3 ANSWER

(a) Merge sort (1 mark)
(b) Any two from: recursive self-calls on both halves (srt calls itself twice) / split at midpoint using LEN DIV 2 / two sub-lists created (L and R) that are separately sorted then joined (1 mark each, max 2)
(c) Advantage: merge sort has O(n log n) efficiency — significantly faster than bubble sort's O(n²) on large datasets (1 mark). Disadvantage: merge sort requires additional memory to store sub-lists during merging; bubble sort is in-place and needs no extra memory (1 mark)

NOTE — IDENTIFYING MERGE SORT vs BINARY SEARCH

Both use DIV 2 to find a midpoint. The difference: binary search eliminates one half and searches the other. Merge sort sorts BOTH halves and merges them. Two recursive calls = merge sort. One search direction = binary search.

COMMON MISTAKES — MERGE SORT

1

Counting the append as a comparison. When one sub-list empties, remaining elements are appended without comparison. Do not count these. In Q2: 5 comparisons, not 6.

2

Confusing merge sort with binary search. Both halve, but merge sort sorts both halves; binary search only searches one.

3

Merging unsorted sub-lists. The merge step only works correctly if both sub-lists are already sorted. You must split all the way to single elements first — single elements are trivially sorted.

4

Getting the merge order wrong. In the final merge, always compare the first (smallest) elements of each sub-list. Never compare elements from non-adjacent positions.

⚡ Exam trace tip: show the split as a top-down tree, then show each merge step clearly labelled from the bottom up. Split phase earns marks. Merge phase earns marks. Both must be shown.

Advantages & Disadvantages

Merge sort — strengths and weaknesses

✓ ADVANTAGES

O(n log n) for all cases — best, average, and worst case are the same. No scenario degrades performance. Reliable and predictable.

Much faster than bubble sort on large data — for large lists, O(n log n) dramatically outperforms O(n²). The efficiency advantage grows with list size.

Stable sort — equal elements maintain their relative order from the original list. Important when sorting records with multiple fields.

⚡ "Give one advantage of merge sort over bubble sort." Answer: merge sort has O(n log n) efficiency in all cases, making it significantly faster than bubble sort's O(n²) for large datasets.

✗ DISADVANTAGES

Requires additional memory — merge sort is not in-place. It needs extra space proportional to the list size to store sub-lists during merging. Bubble sort only needs the original array.

More complex to implement — the recursive structure and separate merge function are harder to write correctly than bubble sort's simple nested loops.

No best-case improvement — unlike optimised bubble sort (O(n) for sorted data), merge sort always does O(n log n) work even on an already-sorted list.

⚡ "Give one disadvantage of merge sort." Answer: it requires additional memory to store sub-lists during the merge phase — it is not an in-place algorithm. Bubble sort does not require this extra memory.

Summary

2.1.3d — Merge Sort

HOW IT WORKS

Split: divide list in half repeatedly until every sub-list has 1 element (base case). Merge: compare first elements of two sorted sub-lists, take the smaller, repeat until one is empty, append remaining. Work up to the full sorted list.

IDENTIFYING FROM CODE — 4 SIGNATURES

(1) Recursive self-calls on both halves. (2) Split at midpoint with DIV 2. (3) Compare first elements: a[0] vs b[0]. (4) Append remaining: return result+left+right.

EFFICIENCY

O(n log n) for ALL cases — best, average, worst. No scenario degrades to O(n²). For large data: enormously faster than bubble sort.

KEY NUMBERS — [6,3,8,2] EXAMPLE

Split to: [6],[3],[8],[2]. First merges: [3,6] and [2,8]. Final merge: [2,3,6,8]. Merge of [3,6]+[2,8] takes 3 comparisons + 1 append.

MERGE SORT vs BUBBLE SORT

Advantage: O(n log n) — far faster on large data. Disadvantage: needs extra memory (not in-place), more complex to implement. Bubble sort is simpler but O(n²) — use merge sort when data is large and performance matters.

2.1.3d Complete

That's Merge Sort done!

Next up: 2.1.3e — Insertion Sort

📝

MARKED WORKSHEET

CSZone.co.uk

🎯

QUIZ

CSZone.co.uk

📊

SLIDES

CSZone.co.uk

Sorting AlgorithmsMerge Sort

By the end of this video you will be able to...

Divide and conquer

Merge sort — step by step

Merge sort pseudocode — for identification

Full worked example — [6, 3, 8, 2]

How merging works — element by element

Exam-style trace — [4, 7, 1, 5]

Efficiency — merge sort

Identifying merge sort from given code

Merge sort — applying the algorithm

Question 3 answered + common mistakes

Merge sort — strengths and weaknesses

2.1.3d — Merge Sort

That's Merge Sort done!

Sorting Algorithms
Merge Sort