Skip to content
Menu

Year 10 (ages 14–15, Grade 9 in the US) · Computing · GCSE programming · Lesson 17

Sorting: merge sort and insertion sort

How merge sort splits a list into single items and merges them back in order, how insertion sort builds a sorted section one item at a time, and how the three sorting algorithms compare.

Exam boards: this lesson matches the AQA and Pearson Edexcel GCSE computing courses. Check which course your school follows.

Whiteboard video lesson: Sorting: merge sort and insertion sort

8-minute video lesson

Teaching, worked examples and 20 practice questions solved step by step.

Watch free for a month

What your child will learn

  • Describe merge sort
  • Trace a merge
  • Describe and trace insertion sort
  • Compare bubble, merge and insertion sort

The method

  1. Merge sort: split until single items, then merge pairs in order.
  2. Merging: compare the fronts of two sorted lists; take the smaller.
  3. Insertion sort: take the next item; insert it into the sorted part.
  4. Compare: speed, memory, simplicity.

Key words: merge sort, insertion sort, divide and conquer, merge, efficiency.

Worked examples

Worked examples from the lesson, with every step.

Question 1

Split [8, 3, 5, 1] fully for merge sort.

  1. Step 1: [8, 3] [5, 1]
  2. Step 2: [8] [3] [5] [1]

Answer: [8] [3] [5] [1]

Question 2

Merge back: what are the two sorted pairs, then the final list?

  1. Step 1: [3, 8] and [1, 5]
  2. Step 2: [1, 3, 5, 8]

Answer: [1, 3, 5, 8]

Question 3

Merge [2, 7] with [3, 4]. Show the order items are taken.

  1. Step 1: 2 vs 3 → 2; 7 vs 3 → 3; 7 vs 4 → 4
  2. Step 2: then 7

Answer: [2, 3, 4, 7]