Sort It Out
The two named sorting algorithms: how a bubble sort compares and swaps neighbours pass by pass, how a merge sort splits a list and merges it back in order, and how they compare on speed and memory.
Get the method right under pressure
Free interactive practice on the steps that lose marks under exam pressure.
Start revising freeWhat you'll cover
Two ways to sort
Putting a list in order is such a common job that computer scientists study set ways to do it. This module covers the two you need: a bubble sort, which compares neighbours and swaps them, and a merge sort, which splits the list up and merges it back in order. You will practise showing the list at each stage, which is what exams ask for.
Sorting vocabulary
Learn these four terms before you sort a list.
Bubble against merge
The two sorts work in very different ways.
Show every stage
A top answer never jumps straight to the sorted list. For a bubble sort, write the list after each pass, showing every swap. For a merge sort, show the splits down to single items and then each merge back together. The marks are in the working, so set out the stages one by one.
Match the term
- bubble sort
- merge sort
- pass
- swap
- works by comparing neighbours
- works by splitting and merging
- one full run through the list
- exchanging two items in the wrong order
Match the feature
- compares neighbours
- divide and conquer
- uses little extra memory
- uses more memory
- a way to describe a bubble sort
- a way to describe a merge sort
- a strength of the bubble sort
- a cost of the merge sort
After one pass
A bubble sort works on the list 5, 3, 8, 1. What is the list after one full pass?
- 3, 5, 1, 8
- 1, 3, 5, 8
- 5, 3, 8, 1
- 3, 8, 5, 1
True of merge sort
Select the TWO statements that are true of a merge sort.
- It splits the list in half again and again.
- It uses more memory than a bubble sort.
- It only ever compares neighbours.
- It never needs any extra memory.
Order the merge sort
Put the stages of a merge sort in order, earliest first.
- Split the list into halves
- Keep splitting until each part is one item
- Merge the single items into ordered pairs
- Merge the parts into one sorted list
Complete the facts
A _____ sort compares items next to each other and swaps them if they are in the wrong order. A _____ sort splits the list in half again and again, then merges the parts back in order. One run through the list in a bubble sort is called a _____. A merge sort uses more _____ than a bubble sort. Merge sort is an example of _____ and conquer.
Count the passes
A bubble sort runs on a list of 5 items. The most passes it can need is one less than the number of items. Subtract 1 from 5 to find the most passes. What is the answer?
Spot the bubble facts
Tap the TWO statements that are true of a bubble sort.
- it compares items next to each other
- it swaps items that are out of order
- it splits the list in half
- it needs a lot of extra memory
Pick the sort
Read each situation and choose the best answer.
- A very large list must be sorted as quickly as possible. Which sort is usually better?
- A short list must be sorted using as little extra memory as possible. Which is simplest?
- A merge sort has split the list down to single items. What happens next?
Compare the sorts
Explain how a bubble sort and a merge sort work and how they compare.
- Explain how a bubble sort works, using passes and swaps
- Explain how a merge sort works, using splitting and merging
- Compare the two on speed and on memory