Sorting and searching

Years 4 to 11

Computers sort lists by comparing neighbours, and search sorted lists by halving them again and again.

One pass of a bubble sort: the 5 swaps its way to the end of 5, 2, 4, 1, 3.

For learners

To sort a list, a computer compares two neighbours. If they are the wrong way round, it swaps them. It does this all the way along the list.

After one pass, the biggest number has bubbled to the end. Repeat the passes, and the whole list ends up in order. This is called a bubble sort.

Once a list is sorted, you can search it fast: look in the middle, throw away the half that cannot hold your number, and repeat.

A worked example

How many checks does binary search need, at most, for a sorted list of 16 items?

Each check halves the list: 16, 8, 4, 2, 1.
That is 4 halvings, plus one last check.
At most 5 checks.

For grown-ups

Bubble sort is slow but easy to follow, and it is a good first example of an algorithm. Binary search needs a sorted list and halves the possibilities each time, so a list of a million items takes only about 20 checks. Comparing these shows why choosing a clever algorithm matters as data grows.

Common mistakes

Stopping after one pass and thinking the list is sorted.
Trying binary search on a list that is not sorted.
Counting the checks wrongly: each check halves what is left.

Why it matters

Search engines, shops and maps all sort and search huge lists every second.

Topics in quarter that use this

Sorting step by step
Binary search
How fast does the work grow?