AQA 8525 · Section 3.1 · 3.1.4b

Merge
Sort

Divide & Conquer · Split and Merge · More Efficient than Bubble

CSZoneAQA GCSE Computer Science 8525

Learning Objectives

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

Describe how merge sort uses divide and conquer

Show the splitting and merging stages of a merge sort

Compare merge sort efficiency with bubble sort

State when merge sort is preferred over bubble sort

How It Works

Merge Sort — Two Phases

PHASE 1 — SPLIT

Keep splitting the list in half until every sub-list has just 1 item

A list of 1 item is always sorted by definition

PHASE 2 — MERGE

Merge pairs of sub-lists back together in sorted order

Compare the first elements of each pair; always take the smaller one first

Divide and Conquer:Break into smallest possible parts, solve each, then combine the solutions.

Worked Example

Sorting [5, 3, 8, 1]

Follow the split → merge process:

5

3

8

1

Original list

5

3

|

8

1

Split into halves

5

|

3

|

8

|

1

Single items (sorted)

3

5

|

1

8

Merge pairs in order

1

3

5

8

✓ Final merged & sorted!

Comparison

Merge Sort vs Bubble Sort

Feature	Bubble Sort	Merge Sort
Approach	Compare adjacent pairs	Divide and conquer
Worst case	~n² comparisons	~n log₂(n) comparisons
Best case	n-1 (sorted list)	n log₂(n)
Best for	Small lists	Large lists

⚡ AQA Exam:Merge sort is always more efficient for large datasets. Learn to show the tree diagram (split levels).

Exam Practice

Have a go at this question

AQA-style question

Show the stages of a merge sort applied to the list [7, 2, 9, 4, 6]. Include the split and merge stages in your answer.

4 marks

MARK SCHEME

Split: [7,2,9,4,6] → [7,2] [9,4,6] → [7][2] [9][4,6] → [7][2][9][4][6] [1]
Merge: [2,7][4,9][6] → [2,7][4,6,9] → [2,4,6,7,9] [1]
All single items shown [1] · Final correct order [1]

Key Takeaways

What to Remember

Merge sort uses divide and conquer — split to single items, then merge in order

Worst case: n log₂(n) comparisons — much better than bubble sort's n²

More efficient than bubble sort for large datasets

Two phases: Split (halve repeatedly) then Merge (combine in sorted order)