Why is binary search faster than linear search on large sorted lists?

Because it removes half of the remaining list each time instead of checking items one by one.

Do I have to memorise the exact code for bubble sort?

No. You need to understand how the algorithm works and how to apply it.

Why is merge sort described as split then merge?

Because it first breaks the list into smaller groups and then merges those groups back together in order.

2.1.3

Searching and Sorting Algorithms

You do not need to memorise exact code for the standard searching and sorting algorithms, but you do need to understand how they work, what their main steps are, and when they can be used.

13 exam questions 8 flashcards

What you need to know

Describe the main steps of linear and binary search.
Explain the main steps of bubble sort, merge sort, and insertion sort.
Apply the algorithms to a given data set.
Know the pre-requisite for binary search and identify each algorithm from a description.

Searching

Linear search and binary search

The key point to remember is that binary search only works on sorted data.

Try it — search and sort stepper

Step through each algorithm so you can see what changes from one stage to the next.

AlgorithmBinary searchStep1 / 3Target22

Start in the middle: 14. The target is bigger, so ignore the left half.

Algorithm	How it works	Key condition
Linear search	Checks each item in turn	Can be used on unsorted data
Binary search	Checks the middle item and halves the search area each time	List must already be sorted

High-value exam point

If the list is not sorted, binary search cannot be used correctly.

Sorting 1

Bubble sort

Bubble sort works in passes through the list.

Compare neighbouring items.
Swap them if they are in the wrong order.
Keep making passes until no swaps are needed.

Sorting 2

Merge sort

Merge sort is easier to understand if you think of it in two phases: split, then merge.

Split the list into smaller groups until each part is very small.
Merge the groups back together in the correct order.
The merging stage is where the ordering happens.

Sorting 3

Insertion sort

Insertion sort builds a sorted list one item at a time.

Take the next item from the unsorted section.
Move through the sorted section until the correct position is found.
Insert the item there and repeat.

High-Value Exam Skill

Recognising and applying the algorithms

You may be shown code, pseudocode, or a worked example and asked which algorithm it is.

If it checks one item after another, think linear search.
If it keeps using the middle of a sorted list, think binary search.
If neighbours keep swapping over several passes, think bubble sort.
If it splits then merges, think merge sort.
If it inserts each item into an already sorted section, think insertion sort.

Not required

You do not need to memorise the exact code or exam reference language for these algorithms.

Key takeaways

Linear search checks items one by one until the item is found or the list ends.
Binary search repeatedly checks the middle of a sorted list and discards half the search area each time.
Bubble sort compares neighbouring items and swaps them if they are in the wrong order.
Merge sort splits the list into smaller parts before merging them back in order.
Insertion sort builds a sorted section by inserting each new item into the correct place.

Glossary

Linear search: Searching one item at a time through a list.
Binary search: Searching a sorted list by repeatedly checking the middle item.
Bubble sort: A sorting algorithm that swaps neighbouring items over repeated passes.
Merge sort: A sorting algorithm that splits data into smaller parts and merges them in order.
Insertion sort: A sorting algorithm that inserts each item into the correct place in a sorted section.

Test yourself

Common questions