Implement and trace bubble sort and insertion sort, analyse their complexity, and compare their behaviour on nearly sorted data

What this dot point is asking

SEAB wants you to implement and trace bubble sort and insertion sort, analyse their complexity, and compare how they behave - especially on nearly sorted data. The central idea is that both are simple $O(n^2)$ comparison sorts, but insertion sort is adaptive: it does far less work when the input is already close to sorted.

The answer

Bubble sort

Bubble sort repeatedly walks the list comparing adjacent pairs and swapping any that are out of order. After each full pass the largest remaining element has "bubbled" to its correct place at the end:

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

With $n$ elements it does about $\dfrac{n(n-1)}{2}$ comparisons, so $O(n^2)$. The early-exit flag makes its best case $O(n)$ on already-sorted data.

Insertion sort

Insertion sort builds a sorted region at the front, taking each new element and shifting it left into place:

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]   # shift right
            j = j - 1
        data[j + 1] = key
    return data

Worst case (reverse order) each element shifts past all before it: $O(n^2)$. Best case (already sorted) each element needs no shift: $O(n)$.

Behaviour on nearly sorted data

This is where they differ in practice. Insertion sort is adaptive: if most elements are already near their final places, each does only a few shifts, so the run is close to linear. Bubble sort with the early-exit flag also benefits, but typically performs more swaps. For small or nearly sorted lists, insertion sort is the usual choice and is used as the base case inside faster sorts.

Examples in context

Example 1. Sorting a hand of cards. Most people sort playing cards by insertion: pick up each card and slide it into the right spot among the cards already in order. The everyday method is exactly the insertion sort algorithm, and it feels fast because a hand is small and often nearly sorted.

Example 2. The base case of a fast sort. Production sorting libraries switch to insertion sort once a sublist is small (say under 16 elements), because its low overhead beats the recursion of merge sort or quicksort on tiny inputs. Its adaptive, low-constant behaviour makes it the ideal finisher.

Try this

Q1. After one full pass of bubble sort, what is guaranteed about the list? [1 mark]

• Cue. The largest unsorted element has moved to its correct final position at the end.

Q2. State the best-case complexity of insertion sort and the input that produces it. [2 marks]

• Cue. $O(n)$ - on an already-sorted list, since each element needs no shifting.

Q3. Why is insertion sort preferred over bubble sort for nearly sorted data? [2 marks]

• Cue. It is adaptive: each element shifts only as far as needed, so few moves occur, approaching a single linear pass.