Bubble Sort & Insertion Sort: How They Work & Their Complexity (OCR A-Level CS 2.3.1)
OCR A-Level CS 2.3.1: how bubble sort and insertion sort work, step-by-step traces, their O(n²) complexity, and when each is used.
Free Bubble Insertion Sort revision resources (OCR A-Level Computer Science, 2.3.1)
We’ve made exam-style practice for this exact topic, free to download: Bubble Insertion Sort question sheet, mark scheme and cheat sheet. Grab them, have a go, then read the full guide below.
The two simplest sorting algorithms on the spec are bubble sort and insertion sort. They are not the fastest, but they are easy to understand, easy to trace, and a guaranteed Paper 2 topic. Spec point 2.3.1(f) expects you to know how each works, be able to trace it, and state its complexity. Both are O(n²), and I'll show you exactly why.
Bubble sort
A bubble sort repeatedly steps through the list, comparing each pair of adjacent items and swapping them if they're in the wrong order. After each full pass the largest remaining item has "bubbled" to its correct place at the end, so the next pass can ignore it. It stops when a pass makes no swaps (the list is sorted).
Tracing [5, 1, 4, 2, 8]:
Pass | List after pass | Swaps made? |
|---|---|---|
1 | [1, 4, 2, 5, 8] | yes |
2 | [1, 2, 4, 5, 8] | yes |
3 | [1, 2, 4, 5, 8] | no → stop |
After pass 1, the largest value (8) is already in place; after pass 2 the list is sorted, and pass 3 confirms it with no swaps.
Insertion sort
An insertion sort builds the sorted list one item at a time. It takes the next item and inserts it into its correct position among the items already sorted to its left, shifting larger items right to make room. (It's how most people sort a hand of cards.)
Tracing [5, 1, 4, 2, 8], where the bold part is the sorted portion:
Step | List | Inserted |
|---|---|---|
start | [5, 1, 4, 2, 8] | (none) |
1 | [1, 5, 4, 2, 8] | 1 |
2 | [1, 4, 5, 2, 8] | 4 |
3 | [1, 2, 4, 5, 8] | 2 |
4 | [1, 2, 4, 5, 8] | 8 |
Each item is slotted into place until the whole list is sorted.
Complexity and comparison
This is the most important part, and it is the bit examiners love: both are O(n²) in the worst case, because each uses a loop inside a loop. For each of n items you may compare or shift up to n others. That is fine for small lists but painfully slow for large ones (a million items is roughly 10¹² operations).
Bubble sort | Insertion sort | |
|---|---|---|
How | Swap adjacent pairs; largest bubbles to the end | Insert each item into the sorted left part |
Worst case | O(n²) | O(n²) |
Best case (nearly sorted) | O(n), one clean pass | O(n), little shifting |
In place? (no extra list) | Yes | Yes |
Insertion sort is usually a bit more efficient in practice and great on nearly-sorted data; bubble sort is mainly valued for being the easiest to understand. Both are beaten by merge and quick sort (O(n log n)) on large data, which is the subject of the next post.
Worked example: one bubble-sort pass
Take [5, 1, 4, 2, 8] and do pass 1 in detail:
compare 5 & 1 → swap →
[1, 5, 4, 2, 8]compare 5 & 4 → swap →
[1, 4, 5, 2, 8]compare 5 & 2 → swap →
[1, 4, 2, 5, 8]compare 5 & 8 → in order, no swap →
[1, 4, 2, 5, 8]
End of pass 1: 8 is in place at the end, and the largest value among the rest (5) has moved right. That's the "bubbling" that gives the algorithm its name.
Common exam mistakes
These are the slips I see most, and none of them are hard to avoid.
Not stopping early. Bubble sort can stop when a pass makes no swaps: say so for the best case O(n).
Forgetting the "in place" detail. Both sorts rearrange the same list: no big extra array (unlike merge sort).
Wrong complexity. Both are O(n²) worst case (nested loops), not O(n log n).
Muddling the methods. Bubble = swap adjacent pairs; insertion = insert into the sorted part.
Trace tables without each pass/step. Show the list after each pass (bubble) or after each insertion (insertion).
Quick recap
Bubble sort: repeatedly swap adjacent items; the largest bubbles to the end each pass; stop when a pass makes no swaps.
Insertion sort: take each item and insert it into the sorted left part, shifting larger items right.
Both are O(n²) worst case (nested loops); both are in place; both are O(n) on nearly-sorted data.
They're simple but slow on large lists: merge/quick sort (O(n log n)) scale far better.
Trace bubble by listing the array after each pass; insertion after each insertion.
Do not just read these traces, redo them. Take a five-item list, scramble it, and run a bubble sort and an insertion sort by hand, writing the list after each pass. Once you have done that, the "trace the algorithm" questions become almost automatic, and you will never confuse the two methods again. Stick with it, you have got this.
Frequently asked questions
How does a bubble sort work? A bubble sort repeatedly passes through the list, comparing each pair of adjacent items and swapping them if they are in the wrong order. After each pass the largest remaining item has moved to its correct place at the end, and the algorithm stops when a complete pass makes no swaps, which means the list is sorted.
How does an insertion sort work? An insertion sort builds the sorted list one item at a time. It takes the next item and inserts it into its correct position among the items already sorted to its left, shifting larger items to the right to make room. This is repeated until every item has been inserted and the list is sorted.
What is the time complexity of bubble sort and insertion sort? Both have a worst-case time complexity of O(n²), because each uses a loop nested inside another loop. On a list that is already nearly sorted both can perform in O(n) in the best case, but for large unsorted lists they are slow compared with merge or quick sort.
What is the difference between bubble sort and insertion sort? Bubble sort works by swapping adjacent items so that the largest value bubbles to the end on each pass. Insertion sort works by taking each item in turn and inserting it into the correct place within the already-sorted part of the list. Both are O(n²) and sort in place, but insertion sort is usually a little more efficient in practice.
Why are bubble sort and insertion sort O(n²)? They are O(n²) because they use nested loops: for each of the n items, the algorithm may need to compare or shift it against up to n other items, giving roughly n × n operations in the worst case. This makes the number of operations grow with the square of the list size.
When would you use bubble sort or insertion sort instead of a faster sort? They are suitable for small lists, or for lists that are already nearly sorted, where their simplicity is an advantage and the O(n²) cost is small. They also sort in place without needing extra memory. For large unsorted lists, an O(n log n) sort such as merge or quick sort is far better.
