Revision notes for AQA GCSE Computer Science Sorting algorithms. Open the guide for explanations and worked examples. Written against the AQA GCSE Computer Science (8525) specification, so the content matches what's examinable rather than general Computer Science background.
Sorting algorithms
What you'll learn
- What a sorting algorithm is and why sorting data is useful.
- How bubble sort works using comparisons, swaps and passes.
- How merge sort works by splitting and merging lists.
- How to compare bubble sort and merge sort in GCSE-style answers.
The basic idea of sorting
A list or array is a collection of items stored in an order. For example:
[7, 2, 9, 4]
Each value in the list is an item. A sorting algorithm rearranges the items into a chosen order.
Definition
Sorting algorithm
A sorting algorithm is a step-by-step method for putting data into a required order, such as ascending order or descending order.
Ascending order means smallest to largest, such as [1, 3, 6, 9].
Descending order means largest to smallest, such as [9, 6, 3, 1].
Sorting is useful because it can make data easier to search, display and understand. For example, a school system might sort students alphabetically by surname, or sort test scores from highest to lowest.
Key actions used in sorting
Before learning the two required algorithms, you need three important terms.
Definition
Comparison, swap and pass
A comparison checks two items to decide which should come first. A swap exchanges the positions of two items. A pass is one complete movement through the part of the list currently being processed.
For example, if sorting in ascending order and you compare 8 and 3, they are in the wrong order because 8 is greater than 3. You would swap them to get 3 then 8.
Key Idea
Sorting is repeated decision-making
Sorting algorithms do not magically “see” the final order. They repeatedly compare items, move them, and gradually make the list more ordered.
Bubble sort
Bubble sort is one of the simplest sorting algorithms to understand. It works by repeatedly comparing adjacent items, meaning items next to each other.
For ascending order:
- Compare the first pair of adjacent items.
- If the left item is greater than the right item, swap them.
- Move one position along and compare the next adjacent pair.
- Continue to the end of the unsorted part of the list.
- Repeat passes until the list is sorted.
After each full pass, the largest unsorted item has “bubbled up” to its correct position at the end of the list.
Example
Tracing bubble sort
Sort [6, 2, 5, 1] into ascending order using bubble sort.
-
Start the first pass by comparing adjacent pairs. Compare 6 and 2, then swap because 6 is greater than 2:
[2, 6, 5, 1]. Compare 6 and 5, then swap:[2, 5, 6, 1]. Compare 6 and 1, then swap:[2, 5, 1, 6]. The 6 is now in its final position. -
On the second pass, ignore the final 6 because it is already sorted. Compare 2 and 5, with no swap needed. Compare 5 and 1, then swap:
[2, 1, 5, 6]. The 5 is now in its final position. -
On the third pass, compare 2 and 1, then swap:
[1, 2, 5, 6]. The list is now in ascending order.
Bubble sort in AQA-style pseudo-code
One possible version of bubble sort is:
length ← number of items in numbers
REPEAT
swapped ← False
FOR index ← 0 TO length - 2
IF numbers[index] > numbers[index + 1] THEN
temp ← numbers[index]
numbers[index] ← numbers[index + 1]
numbers[index + 1] ← temp
swapped ← True
ENDIF
ENDFOR
length ← length - 1
UNTIL swapped = False
The variable swapped records whether any swap happened during the pass. If a full pass happens with no swaps, the list must already be sorted.
Common Mistake
Thinking one pass is enough
One pass of bubble sort usually does not sort the whole list. It only guarantees that the largest unsorted item has moved to the end when sorting in ascending order.
Merge sort
Merge sort is a sorting algorithm that uses two main stages:
- Split the list into smaller and smaller sublists.
- Merge the sublists back together in sorted order.
A sublist is a smaller list made from part of the original list. A merge combines two sorted lists into one sorted list.
Merge sort keeps splitting until each sublist contains one item. A one-item list is already sorted, because there is nothing to compare it with. Then the algorithm repeatedly merges these small sorted lists to build larger sorted lists.
Key Idea
Merge sort sorts while merging
The splitting stage breaks the problem into tiny pieces. The actual ordering happens when sorted sublists are merged back together.
How merging works
When merging two sorted sublists, compare the first remaining item in each sublist. Move the smaller item into the new merged list. Repeat until all items have been moved.
Example
Merging two sorted sublists
Merge [2, 6, 9] and [1, 3, 8] into one sorted list.
-
Compare the first remaining items: 2 and 1. Choose 1 because it is smaller, so the merged list becomes
[1]. -
Compare 2 and 3. Choose 2, giving
[1, 2]. -
Compare 6 and 3. Choose 3, giving
[1, 2, 3]. -
Compare 6 and 8. Choose 6, giving
[1, 2, 3, 6]. -
Compare 9 and 8. Choose 8, giving
[1, 2, 3, 6, 8]. Only 9 remains, so copy it across to finish:[1, 2, 3, 6, 8, 9].
Common Mistake
Assuming splitting puts items in order
Splitting a list does not sort it. The list becomes sorted only when pairs of already sorted sublists are carefully merged.
Comparing bubble sort and merge sort
Both algorithms sort data, but they do it in very different ways.
| Feature | Bubble sort | Merge sort |
|---|---|---|
| Main method | Repeatedly compares and swaps adjacent items | Splits the list, then merges sorted sublists |
| Ease of understanding | Very simple to trace | More complex because it has split and merge stages |
| Performance on long unsorted lists | Usually slow because it may need many passes and swaps | Usually much faster for larger lists |
| Extra storage | Needs very little extra storage, usually just a temporary variable | Needs extra temporary lists during merging |
| Useful when | The list is small or nearly sorted | The list is larger and efficient sorting matters |
Bubble sort is easy to write and explain, but it becomes inefficient when the list is large and jumbled. Merge sort is harder to trace, but it is generally a better choice for larger lists because it divides the problem into smaller parts and merges them systematically.
Example
Choosing a sorting algorithm
A program must sort 10,000 unsorted customer records into surname order. Choose between bubble sort and merge sort.
-
Identify the size and state of the data. There are many records, and they are described as unsorted, so repeated adjacent swaps would take a lot of work.
-
Compare the mechanics of the algorithms. Bubble sort would repeatedly pass through the records and swap neighbouring records. Merge sort would split the records into smaller lists and then merge them in order.
-
Choose merge sort because it is generally more efficient for larger unsorted lists. Mention that it may need extra temporary storage, but the speed advantage is usually more important here.
Tip
A simple comparison phrase
A strong exam comparison is: bubble sort is simpler but usually slower; merge sort is more complex but usually faster for larger lists and needs extra storage.
How to explain them clearly
For bubble sort, focus on these words:
- adjacent items
- compare
- swap if in the wrong order
- repeat passes
- largest item moves to the end
For merge sort, focus on these words:
- split into sublists
- continue until one-item lists
- merge sorted sublists
- compare first remaining items
- build the final sorted list
Exam technique
In the exam
-
If asked to trace bubble sort, show the list after each comparison or each pass, depending on what the question asks. Do not skip swaps.
-
If asked to trace merge sort, show both stages: splitting down to single items and merging back into sorted lists.
-
If asked to compare them, give a balanced answer: mention simplicity, speed on larger lists, and extra storage.
Self review
Check yourself
- Why does the largest unsorted item move to the end after a bubble sort pass?
- During merge sort, why is a one-item list already sorted?
- Give one advantage of bubble sort and one advantage of merge sort.
Recap questions
Test yourself with 5 quick questions on this guide. Answer them all correctly to complete it.
You've reached the end
Test yourself on this topic, or move on to the next guide.
How was this guide?