Key Stage 3 computing · Algorithms

KS3 computing: sorting algorithms (bubble, merge, insertion)

A sorting algorithm puts data in order, for example numbers from smallest to largest or names alphabetically. At Key Stage 3, students study and trace several sorting algorithms, with bubble sort, insertion sort and merge sort being the usual examples, and begin to explain why one method suits a situation better than another. Sorting is one of the standard examples the curriculum gives of a key algorithm.

Sorting algorithms, explained

The national curriculum asks Key Stage 3 pupils to understand several key algorithms that reflect computational thinking, with sorting and searching named as examples, and to compare alternatives using logical reasoning. Schools choose which sorting algorithms to teach. Bubble sort, insertion sort and merge sort are the common ones, and a school may teach some or all of them. All three do the same job but go about it in different ways, which is why they are taught together.

Bubble sort works along the list comparing each pair of neighbouring items and swapping them if they are in the wrong order. After one pass, the largest item has “bubbled” to the end. The process repeats, each time with one fewer item to check, until a full pass makes no swaps. It is easy to understand and to program, but it makes a lot of comparisons, so it slows down quickly on long lists.

Insertion sort works the way many people sort a hand of playing cards. It treats the first item as a sorted list of one, takes the next item and slides it back into the right place among those already sorted, and repeats until every item has been placed. It is simple and efficient for short or nearly sorted lists. Merge sort uses a different idea, called divide and conquer: split the list in half again and again until each piece has one item, then merge pairs of sorted pieces back together, always taking the smaller front item first. Merging 2, 5 with 1, 9 gives 1, 2, 5, 9.

Students trace each algorithm by hand, with counters, cards or tables, and then write or complete code for at least one of them. They are encouraged to ask logical questions: how many comparisons or swaps were needed, what happens if the list is already in order, what if it is in reverse, and why is merge sort usually much faster on large lists? Computers sort constantly, from ordering search results to arranging a contact list, so the ideas are far from abstract. Comparing algorithms is covered in more depth on its own page.

Words your child will hear

Sort: To arrange items in a given order, such as smallest to largest or A to Z.
Pass: One complete run through the list by an algorithm such as bubble sort.
Swap: Exchanging the positions of two items.
Comparison: Checking which of two items should come first.
Merge: Combining two sorted lists into one sorted list.
Divide and conquer: Solving a problem by splitting it into smaller pieces, solving those and combining the results.
Ascending: In order from smallest to largest.

What the National Curriculum says

The programme of study for Key Stage 3 says:

Pupils should be taught to understand several key algorithms that reflect computational thinking [for example, ones for sorting and searching]; use logical reasoning to compare the utility of alternative algorithms for the same problem
Aim: pupils can understand and apply the fundamental principles and concepts of computer science, including abstraction, logic, algorithms and data representation.

Objectives from the National Curriculum in England, © Crown copyright, used under the Open Government Licence v3.0.

A worked example

Use bubble sort to put 5, 2, 9, 1, 6 into ascending order. Show each pass.

Pass 1. Compare neighbours from the left. 5 and 2 are out of order, so swap. 5 and 9 are fine. 9 and 1 are out of order, so swap. 9 and 6 are out of order, so swap. The largest value, 9, is now at the end.
```
5 2 9 1 6
2 5 9 1 6  (swap 5,2)
2 5 1 9 6  (swap 9,1)
2 5 1 6 9  (swap 9,6)
```
Pass 2. Check the pairs again, but the last item is already in place. 2 and 5 are fine. 5 and 1 are out of order, so swap. 5 and 6 are fine.
```
2 5 1 6 9
2 1 5 6 9  (swap 5,1)
```
Pass 3. 2 and 1 are out of order, so swap. 2 and 5 are fine.
```
2 1 5 6 9
1 2 5 6 9  (swap 2,1)
```
Pass 4. Only the first pair is left to check: 1 and 2 are fine. A pass with no swaps tells the algorithm that the list is sorted, so it stops.
```
1 2 5 6 9  (no swaps)
```
Count the work. There were 5 swaps in total. That matches the number of pairs that began in the wrong order: (5,2), (5,1), (2,1), (9,1) and (9,6).

The sorted list is 1, 2, 5, 6, 9. Bubble sort needed four passes (the last with no swaps) and five swaps.

Common mistakes and how to help

Stopping after one pass of bubble sort

After the first pass the largest item is in place, and students assume that the work is finished because the list looks nearly right.

What helps: Keep going until a full pass has no swaps. Trace a list in reverse order to see how many passes can be needed.

Mixing up swapping with overwriting

When writing code, copying one value over another loses the original value. Students forget that a swap needs somewhere temporary to hold one value.

What helps: Use two cups and a third empty cup to swap their contents. The third cup is the temporary variable.

Thinking all sorting algorithms are equally good

Each one produces the same final order, so it seems the choice makes no difference.

What helps: Compare the amount of work for the same list, for example by counting comparisons, and try a long list. Merge sort usually does far less work than bubble sort on big lists, though bubble sort is easier to write.

Thinking merge sort sorts the items at the splitting stage

The diagrams show the list being broken into pieces, and students assume the ordering happens as the list splits.

What helps: Splitting does no sorting at all. The ordering happens as pieces are merged back together, by repeatedly taking the smaller front item from each sorted piece.

How to help at home

Sort a hand of cards. Deal five cards and sort them into order, then ask your child to describe exactly what they did. Many people use insertion sort without knowing it.
Be the bubble sort. Line up four or five family members, or soft toys, with different heights. Only neighbours may compare and swap. See how many passes it takes, and whether the number is different if the line starts almost in order.
Race two methods. Write ten numbers on slips of paper. Sort them using bubble sort, then merge sort, counting each comparison. Compare the two counts and ask which was easier and which needed fewer steps.
Ask for a trace. Ask your teenager to show you a trace table from class. Check the method rather than the answer by asking, “What would happen on the next pass?”
Notice sorting in daily life. Sorting a playlist by length, a shop’s prices from low to high or a league table are all sorting. Ask what the computer is comparing and how it knows which comes first.

Builds on

Key Stage 2: Designing, writing and debugging programs
Key Stage 2: Controlling and simulating physical systems
Key Stage 2: Decomposition: breaking problems down
Key Stage 2: Sequence in programs
Key Stage 2: Selection: if and else
Key Stage 2: Repetition and loops
Key Stage 2: Variables, input and output
Key Stage 2: Explaining how algorithms work
Key Stage 2: Debugging algorithms and programs