Bubble Sort and Insertion Sort

Sorting — arranging data into a defined order — is, alongside searching, one of the two great staple operations of computing, and the OCR H446 specification expects you to know four sorting algorithms in detail. This lesson covers the two simplest: bubble sort and insertion sort. Both are $O(n^2)$O(n2) "quadratic" sorts, which makes them poor choices for large data, yet they remain essential to learn: they are easy to trace by hand, they illustrate ideas (in-place sorting, stability, adaptivity, best/worst/average analysis) that recur throughout the course, and the exam routinely asks you to show the state of an array after each pass. We trace each algorithm pass by pass, derive its complexity in every case, and finish with the judgement question the exam loves: which algorithm, and why. Treat the tracing as a skill to be practised rather than a fact to be memorised — the marks come from showing the array's evolving state correctly, step by step, exactly as you would on a real exam paper.

---

Spec Mapping

This lesson supports the sorting algorithms content of OCR H446 section 2.3 (algorithm design and analysis), with links to 1.4 data structures and to the complexity material of 2.3. Paraphrased, the assessable points are:

• Knowing the operation of bubble sort and insertion sort and being able to trace each on given data, showing the array after each pass or insertion.
• Stating and explaining the time complexity of each algorithm in best, worst and average cases using Big-O notation, and giving the space complexity.
• Understanding sorting properties — in-place operation, stability and adaptivity — and using them to compare algorithms.
• Justifying which sorting algorithm is most appropriate for a given problem, data size and data state.

We paraphrase throughout; verify exact wording against the current OCR H446 specification.

---

Why Sort Data?

Putting data into ascending or descending order is rarely the end goal — it is the enabler for many faster operations:

• Binary search becomes possible — $O(\log n)$O(logn) lookups instead of $O(n)$O(n) (see the searching lesson).
• Duplicate detection and finding the median or extremes become trivial — equal items sit adjacent, and the smallest/largest are at the ends.
• Merging two data sets, and many database join and group-by operations, are far cheaper on sorted input.
• Human-facing output (leaderboards, alphabetical lists, price-sorted results) almost always requires a sort.

Because sorting is so foundational, computer scientists have studied it exhaustively — there are dozens of named sorting algorithms, each making a different trade-off between time, space, stability and simplicity. The two algorithms in this lesson are the entry point to that study: they are the simplest to understand and to trace, which makes them ideal for learning the vocabulary of sorting (passes, comparisons, swaps, in-place, stable, adaptive, best/worst/average case) that you will reuse when you meet the faster algorithms next. Master the vocabulary here and the more advanced sorts become much easier to reason about.

---

Bubble Sort

Bubble sort repeatedly steps through the list comparing adjacent elements and swapping them when they are out of order. On each pass the largest unsorted element "bubbles" to its correct place at the end — hence the name.

The algorithm in words

1. Start at the front of the list.
2. Compare each adjacent pair; if the left is greater than the right, swap them.
3. One full sweep is a pass; after it, the largest unsorted value has reached its final position at the end.
4. Repeat, each pass needing one fewer comparison (the tail is already sorted).
5. If a whole pass makes no swaps, the list is already sorted and the algorithm can stop early.

Pseudocode (OCR style)

The swapped flag is what makes this version adaptive — it lets the algorithm finish early on already-sorted (or nearly sorted) data:

# OCR-style pseudocode
procedure bubbleSort(data, size)
    for i = 0 to size - 2
        swapped = false
        for j = 0 to size - 2 - i        // shrinking inner range
            if data[j] > data[j + 1] then
                temp = data[j]
                data[j] = data[j + 1]
                data[j + 1] = temp
                swapped = true
            endif
        next j
        if swapped == false then
            return                        // already sorted — exit early
        endif
    next i
endprocedure

Python implementation

def bubble_sort(data):
    n = len(data)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            if data[j] > data[j + 1]:
                data[j], data[j + 1] = data[j + 1], data[j]
                swapped = True
        if not swapped:
            break               # already sorted
    return data

Fully worked example — sorting [5, 3, 8, 1, 2]

Pass 1 (inner loop compares indices 0–3; the bold value reaches its final home):

Compare	Values	Swap?	Array after
data[0] vs data[1]	5 > 3	Yes	[3, 5, 8, 1, 2]
data[1] vs data[2]	5 < 8	No	[3, 5, 8, 1, 2]
data[2] vs data[3]	8 > 1	Yes	[3, 5, 1, 8, 2]
data[3] vs data[4]	8 > 2	Yes	[3, 5, 1, 2, 8]

Pass 2 (inner loop now only needs indices 0–2):

Compare	Values	Swap?	Array after
data[0] vs data[1]	3 < 5	No	[3, 5, 1, 2, 8]
data[1] vs data[2]	5 > 1	Yes	[3, 1, 5, 2, 8]
data[2] vs data[3]	5 > 2	Yes	[3, 1, 2, 5, 8]

Pass 3 (indices 0–1):

Compare	Values	Swap?	Array after
data[0] vs data[1]	3 > 1	Yes	[1, 3, 2, 5, 8]
data[1] vs data[2]	3 > 2	Yes	[1, 2, 3, 5, 8]

Pass 4 (index 0 only): data[0]=1 < data[1]=2 — no swap. Because no swap occurred in this pass, swapped stays false and the algorithm terminates early. The fully sorted array is [1, 2, 3, 5, 8].

Exam Tip: When asked to show bubble sort "after each pass", give the whole array at the end of every pass and mark which element is now fixed. Examiners award marks per correct pass, so a single mis-traced swap costs only one mark if the rest follows correctly from your (wrong) state.

A second example — the value of the early-exit flag

To see why the swap flag matters, trace bubble sort on the nearly sorted array [1, 2, 4, 3, 5], where only one pair is out of place:

Pass 1:

Compare	Values	Swap?	Array after
data[0] vs data[1]	1 < 2	No	[1, 2, 4, 3, 5]
data[1] vs data[2]	2 < 4	No	[1, 2, 4, 3, 5]
data[2] vs data[3]	4 > 3	Yes	[1, 2, 3, 4, 5]
data[3] vs data[4]	4 < 5	No	[1, 2, 3, 4, 5]

Pass 2: the inner loop makes three comparisons (1<2, 2<3, 3<4) and no swaps, so swapped remains false and the algorithm exits. The list was sorted after a single corrective swap. Without the flag, bubble sort would blindly grind through all four passes regardless — wasting roughly $O(n^2)$O(n2) work on data that was almost ready. This is exactly why the best case is $O(n)$O(n) only when the flag is present, and it is the most common thing candidates forget to mention.

Complexity

Case	When	Comparisons	Complexity
Best	Already sorted (early exit)	$n - 1$n−1	$O(n)$O(n)
Average	Random order	about $\frac{n(n-1)}{4}$4n(n−1)​	$O(n^2)$O(n2)
Worst	Reverse sorted	$\frac{n(n-1)}{2}$2n(n−1)​	$O(n^2)$O(n2)

The worst case arises because the two nested loops each run up to n times: $\frac{n(n-1)}{2}$2n(n−1)​ comparisons, which is $O(n^2)$O(n2). Space complexity is $O(1)$O(1) — bubble sort rearranges the array in place, using only a single temporary variable for swaps.

---

Insertion Sort

Insertion sort grows a sorted region at the front of the array one element at a time. It takes the next unsorted element (the key) and inserts it into its correct place among the already-sorted elements by shifting larger ones to the right.

Analogy

It is exactly how most people sort a hand of playing cards: you keep the cards you have arranged, pick up the next card, and slide it left until it sits in the right place.

The algorithm in words

1. Treat element 0 as a sorted region of size one.
2. Take the next element as the key.
3. Compare the key leftwards against the sorted region, shifting each larger element one place right.
4. Drop the key into the gap that opens up.
5. Repeat until every element has been inserted.

Pseudocode (OCR style)

# OCR-style pseudocode
procedure insertionSort(data, size)
    for i = 1 to size - 1
        key = data[i]
        j = i - 1
        while j >= 0 AND data[j] > key
            data[j + 1] = data[j]        // shift larger element right
            j = j - 1
        endwhile
        data[j + 1] = key                // drop key into the gap
    next i
endprocedure

Python implementation

def insertion_sort(data):
    for i in range(1, len(data)):
        key = data[i]
        j = i - 1
        while j >= 0 and data[j] > key:
            data[j + 1] = data[j]
            j -= 1
        data[j + 1] = key
    return data

Fully worked example — sorting [5, 3, 8, 1, 2]

The vertical bar shows the boundary between the sorted region (left) and the unsorted region (right):

i	key	Sorted region before	Shifts performed	Array after insertion
1	3	[5]	5 > 3 → shift 5	[3, 5 | 8, 1, 2]
2	8	[3, 5]	8 > 5 → none	[3, 5, 8 | 1, 2]
3	1	[3, 5, 8]	8,5,3 all > 1 → shift all three	[1, 3, 5, 8 | 2]
4	2	[1, 3, 5, 8]	8,5,3 > 2; stop at 1	[1, 2, 3, 5, 8]

The fully sorted array is [1, 2, 3, 5, 8]. Notice insertion sort performs shifts, not swaps — and the number of shifts for each key equals how far it must travel, which is why nearly sorted data is so cheap to sort this way.

Complexity

Case	When	Comparisons	Complexity
Best	Already sorted	$n - 1$n−1	$O(n)$O(n)
Average	Random order	about $\frac{n(n-1)}{4}$4n(n−1)​	$O(n^2)$O(n2)
Worst	Reverse sorted	$\frac{n(n-1)}{2}$2n(n−1)​	$O(n^2)$O(n2)

In the best case each key needs just one comparison (it is already $\geq$≥ the element to its left) and the inner while loop exits immediately, giving $O(n)$O(n). In the worst case (reverse order) each key must travel all the way to the front, giving $\frac{n(n-1)}{2}$2n(n−1)​ operations, i.e. $O(n^2)$O(n2). Space complexity is $O(1)$O(1) — like bubble sort, insertion sort works in place.

---

Understanding the Quadratic Growth

Both algorithms are $O(n^2)$O(n2) for the same structural reason, and the exam often asks you to explain it: each has a loop nested inside another loop, with both loops scaling with the input size n. The outer loop runs about n times, and for each of those iterations the inner loop runs up to about n times, so the total work is proportional to $n \times n = n^2$n×n=n2.

A precise count for the worst case is the sum of an arithmetic series. On the first pass of bubble sort the inner loop does $n - 1$n−1 comparisons, on the next $n - 2$n−2, and so on down to 1:

$(n-1) + (n-2) + \cdots + 2 + 1 = \frac{n(n-1)}{2}$(n−1)+(n−2)+⋯+2+1=2n(n−1)​

Expanding gives $\frac{n^2 - n}{2}$2n2−n​. As n grows, the $n^2$n2 term dominates the $-n$−n term and the constant $\frac{1}{2}$21​ is irrelevant to growth rate, so the complexity is reported as $O(n^2)$O(n2). This is the canonical worked example you will revisit in the Big-O lesson: a triangular sum of work collapses to a quadratic class.

The practical consequence is severe. Sorting 1,000 items by bubble or insertion sort takes on the order of $\frac{1000 \times 999}{2} \approx 500{,}000$21000×999​≈500,000 comparisons; sorting 1,000,000 items takes on the order of $5 \times 10^{11}$5×1011 — half a trillion. A divide-and-conquer sort of complexity $O(n \log n)$O(nlogn) would do the latter in about $2 \times 10^7$2×107 operations, roughly 25,000 times fewer. This gulf — visible only at scale — is precisely why the next lesson's merge sort and quick sort exist, and why these two algorithms are confined to small or nearly sorted data in real systems.

It is worth stressing what the best case tells us. Insertion sort's $O(n)$O(n) best case is not a curiosity: real data is often "nearly sorted" (think of appending a few new records to an already-ordered file), and on such data insertion sort genuinely behaves linearly. The lesson is that worst-case Big-O is not the whole story — the distribution of likely inputs matters, which is why an algorithm's best and average cases are examined alongside its worst case.

---

Comparison: Bubble Sort vs Insertion Sort

Feature	Bubble sort	Insertion sort
Best case	$O(n)$O(n) (with swap flag)	$O(n)$O(n)
Average case	$O(n^2)$O(n2)	$O(n^2)$O(n2)
Worst case	$O(n^2)$O(n2)	$O(n^2)$O(n2)
Space	$O(1)$O(1) in place	$O(1)$O(1) in place
Stable?	Yes	Yes
Adaptive?	Yes (only with the flag)	Yes (naturally)
Main operation	Swaps (3 writes each)	Shifts (1 write each)
Typical real-world use	Teaching; tiny lists	Small or nearly sorted lists; as a base case inside bigger sorts