How do binary search and merge sort work for GCSE?

If you're revising algorithms for GCSE Computer Science, four names come up again and again: linear search, binary search, bubble sort, and merge sort. Exam boards love asking you to trace these by hand, spot the runtime, or fill in missing pseudocode lines. Here's what actually matters for the exam and beyond.

Linear search: the baseline

Linear search checks every item in a list, one at a time, until it finds the target or reaches the end. That's it.

for i = 0 to length(list) - 1
    if list[i] == target then
        return i
return -1

Worst case, you check every single element, so it's O(n). Best case, the target is first, so O(1). Examiners like asking you to state both. Linear search works on unsorted data, which is its one real advantage over binary search.

Binary search: the one that trips people up

Binary search only works on a sorted list. You compare the target to the middle item. If the target is smaller, you discard the top half; if larger, discard the bottom half. Repeat until you find it or run out of items.

low = 0
high = length(list) - 1
while low <= high
    mid = (low + high) / 2
    if list[mid] == target then
        return mid
    else if list[mid] < target then
        low = mid + 1
    else
        high = mid - 1
return -1

This is O(log n), which is why it's dramatically faster on large datasets. Search a sorted list of a million items and linear search might need up to a million comparisons; binary search needs about 20. Examiners commonly give you a list of, say, 16 numbers and ask you to trace through which indices get checked — practise this by hand with pen and paper, not just in your head.

Bubble sort: simple but slow

Bubble sort repeatedly walks through the list, swapping adjacent items if they're in the wrong order. Each full pass pushes the largest unsorted item to its correct position at the end.

for i = 0 to length(list) - 1
    for j = 0 to length(list) - 2 - i
        if list[j] > list[j+1] then
            swap(list[j], list[j+1])

Worst case is O(n²) — for every element, you might scan almost the whole list again. It's rarely used in real software because it's slow on large data, but examiners like it because tracing it by hand is manageable and it clearly shows the idea of repeated passes and swaps. Know how to count the number of comparisons and swaps in a trace table; that's a common mark scheme item.

Merge sort: divide and conquer

Merge sort splits the list in half repeatedly until each sublist has one item, then merges those sublists back together in sorted order.

function mergeSort(list)
    if length(list) <= 1 then
        return list
    mid = length(list) / 2
    left = mergeSort(list[0:mid])
    right = mergeSort(list[mid:])
    return merge(left, right)

The merge step compares the front items of each half and picks the smaller one, repeating until both halves are used up. This gives O(n log n), which beats bubble sort comfortably on anything but tiny lists. GCSE questions sometimes ask you to draw the split-and-merge diagram — a tree shape showing the list dividing down and then recombining. Practise drawing this for a list of 8 numbers so you're fast at it under exam conditions.

What examiners actually test

Most mark schemes want you to be able to:

• Trace an algorithm step by step and write down the state of the list after each pass or comparison.
• State time complexity in Big O terms, or at least describe it in words (