GCSE-ready- Home
- Lessons
- KS3 Computing
- Sorting: merge sort and comparing algorithms
Sorting: merge sort and comparing algorithms
🎬 The doodle video for this lesson is coming soon. Subscribe on YouTube to see it first.
Merge sort is a 'divide and conquer' algorithm. It is much faster than bubble sort on big lists, which is why real programs use ideas like it.
Divide
Keep splitting the list in half until every part has just one item. A list of one item is already sorted.
6, 2, 8, 4, 7, 1, 5, 3 splits into 8 single items.
6, 2, 8, 4, 7, 1, 5, 3 splits into 8 single items.
Conquer: merge
Merge pairs of lists into one sorted list by comparing their front items and taking the smaller one each time.
Choosing an algorithm
Merge the sorted lists 2, 5, 9 and 3, 4, 8 into one sorted list.
- Compare 2 and 3: take 2.
- Compare 5 and 3: take 3. Compare 5 and 4: take 4.
- Compare 5 and 8: take 5. Compare 9 and 8: take 8.
- Only 9 is left: take it.
Answer: 2, 3, 4, 5, 8, 9
Merge sort splits a list into single items, then merges them back in order. It is faster than bubble sort on large lists but harder to code and uses more memory. Choose an algorithm by speed, memory and simplicity.
The interactive lesson includes the diagrams for this topic.
Check you have got it
Answer 6 quick questions with instant marking. If you get one wrong, GCSE-ready shows you why and gives you another go. It is free, and you do not need an account.