Skip to content

Searching and sorting algorithms

GCSE Computer Science revision notes, key terms and practice questions.

In short

Check each item in turn, starting at the beginning, until you find the target or reach the end of the list. It works on unsorted lists. It is simple, but slow for large lists: a list of n items may need n comparisons.

For GCSE students in Years 10 and 11, on the AQA, OCR, Edexcel and Eduqas Computer Science courses.

Linear search

  • Check each item in turn, starting at the beginning, until you find the target or reach the end of the list.
  • It works on unsorted lists. It is simple, but slow for large lists: a list of n items may need n comparisons.

Binary search

  • It only works on a sorted list. Look at the middle item. If it is the target, stop. If the target is smaller, discard the upper half; if it is larger, discard the lower half. Repeat on the half that is left.
  • It is much faster for large lists: 1000 items need at most 10 comparisons, because each comparison halves the list.
  • When there are two middle items, pick one of them consistently (for example the lower one).

Bubble sort

  • Go through the list comparing each pair of neighbouring items, and swap them if they are in the wrong order. Each pass moves the largest remaining item to its correct place at the end.
  • Keep making passes until a whole pass makes no swaps.
  • It is simple to code, but slow for large lists.

Merge sort and insertion sort

  • Merge sort: split the list in half again and again until every list has one item, then merge the lists back together in order. It is much faster than bubble sort for large lists, but uses more memory.

Key terms

Linear search
Checking each item in turn until the target is found.
Binary search
Repeatedly checking the middle item of a sorted list and discarding half.
Bubble sort
Repeatedly comparing and swapping neighbouring items until no swaps are needed.
Merge sort
Splitting a list into single items, then merging them back together in order.
Insertion sort
Inserting each item into its correct place in a growing sorted part.
Pass
One complete trip through the list in a sort.

Quick questions on Searching and sorting algorithms

Which search only works on a sorted list?
Binary search: It relies on knowing which half the target is in.
How does a linear search work?
It checks each item in turn from the start: It stops when it finds the target or reaches the end.
In a binary search, the target is smaller than the middle item. What happens next?
The upper half is discarded: The target must be in the lower half.
What is the maximum number of comparisons a binary search needs for 1000 sorted items?
10: 2¹⁰ = 1024, so 10 halvings are enough.
What does a bubble sort compare?
Pairs of neighbouring items: It swaps a pair if they are in the wrong order.
After one pass of a bubble sort into ascending order, where is the largest item?
At the end of the list: It 'bubbles' to the end.
When does a bubble sort stop?
When a pass makes no swaps: No swaps means the list is in order.
What is the first stage of a merge sort?
Split the list in half repeatedly until each list has one item: Then the single items are merged back together in order.

Searching and sorting algorithms: questions and answers

What is one disadvantage of a merge sort compared with a bubble sort?
It uses more memory. It needs extra space for the split lists.
What is one advantage of a linear search?
It works on an unsorted list. Binary search needs the list to be sorted first.
A bubble sort starts on the list 5, 2, 4. What is the list after the first swap?
2, 5, 4. 5 and 2 are compared and swapped first.

Practise Searching and sorting algorithms: 16 questions

Download these notes as a PDF

Previous topic: Pseudocode and flowchartsNext topic: Programming fundamentals

More in Fundamentals of algorithms

LycoLearn is still loading…

This can take a little longer on a busy school or home network. If nothing happens, try refreshing the page.

LycoLearn didn’t load properly

Part of it didn’t arrive. Try refreshing the page in a minute, or open LycoLearn in another browser.