Sorting and Searching Algorithms — GCSE and A Level Guide

Algorithms are at the heart of Computer Science — and sorting and searching algorithms appear in virtually every GCSE and A Level exam. This guide covers everything you need: how each algorithm works, step-by-step traces, complexity analysis, and exam technique.

Why Algorithms Matter

Before we dive in: why do we need different sorting algorithms? Can’t we just use one?

The answer is efficiency. Different algorithms have different time complexities — some are fast with small datasets, others scale much better with large ones. Understanding when to use each algorithm, and why, is as important as knowing how they work.

---

Searching Algorithms

Linear Search

Linear search (also called sequential search) checks each element in order until it finds the target or reaches the end.

How it works:

1. Start at the first element
2. Compare it with the target
3. If it matches, return the position
4. If not, move to the next element
5. Repeat until found or the list is exhausted

Python:

def linear_search(lst, target):
    for i in range(len(lst)):
        if lst[i] == target:
            return i
    return -1  # not found

When to use it:

• The list is unsorted
• The list is small
• You only need to search once (sorting first then binary searching isn’t worth it)

Complexity: O(n) — in the worst case, you check every element.

---

Binary Search

Binary search repeatedly halves the search space by comparing the target with the middle element. It’s much faster than linear search — but requires a sorted list.

How it works:

1. Find the middle element
2. If it equals the target → found!
3. If the target is smaller → search the left half
4. If the target is larger → search the right half
5. Repeat until found or the search space is empty

Worked example:

List: [11, 15, 22, 34, 47, 56, 63, 78, 85, 91] Target: 56

Step	Low	High	Mid index	Mid value	Action
1	0	9	4	47	56 > 47, search right
2	5	9	7	78	56 < 78, search left
3	5	6	5	56	Found! Return 5

Python:

def binary_search(lst, target):
    low = 0
    high = len(lst) - 1
    while low <= high:
        mid = (low + high) // 2
        if lst[mid] == target:
            return mid
        elif lst[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1  # not found

Complexity: O(log n) — each step halves the search space. With 1,000 elements, you need at most 10 comparisons.

Examiner tip: Always show your working in binary search questions. Write down the mid-point calculation explicitly — many marks are available just for correct working even if you make an error later.

---

Sorting Algorithms

Bubble Sort

Bubble sort makes repeated passes through the list, comparing adjacent pairs and swapping them if they’re in the wrong order. The largest unsorted element “bubbles up” to its correct position after each pass.

How it works:

1. Compare element 0 and element 1; swap if out of order
2. Compare element 1 and element 2; swap if out of order
3. Continue to the end — one pass complete
4. After each pass, the last element is in its final position
5. Repeat for (n-1) passes total

Worked trace:

List: [64, 34, 25, 12, 22]

Pass 1:

• 64 > 34 → swap → [34, 64, 25, 12, 22]
• 64 > 25 → swap → [34, 25, 64, 12, 22]
• 64 > 12 → swap → [34, 25, 12, 64, 22]
• 64 > 22 → swap → [34, 25, 12, 22, 64] ← 64 in position

Pass 2:

• 34 > 25 → swap → [25, 34, 12, 22, 64]
• 34 > 12 → swap → [25, 12, 34, 22, 64]
• 34 > 22 → swap → [25, 12, 22, 34, 64] ← 34 in position

Pass 3:

• 25 > 12 → swap → [12, 25, 22, 34, 64]
• 25 > 22 → swap → [12, 22, 25, 34, 64] ← 25 in position

Pass 4:

• 12 < 22 → no swap → [12, 22, 25, 34, 64] ← done

Python:

def bubble_sort(lst):
    n = len(lst)
    for pass_num in range(n - 1):
        swapped = False
        for i in range(n - 1 - pass_num):
            if lst[i] > lst[i + 1]:
                lst[i], lst[i + 1] = lst[i + 1], lst[i]
                swapped = True
        if not swapped:  # optimisation: stop early if no swaps
            break
    return lst

Complexity: O(n²) worst case. Not efficient for large lists.

When to use it: Small lists, or in exam questions. Not used in real-world applications.

---

Insertion Sort

Insertion sort builds a sorted portion of the list one element at a time, inserting each new element into the correct position.

How it works:

1. Start with the second element
2. Compare it with all elements before it (going backwards)
3. Shift elements right until you find the correct position
4. Insert the element there
5. Move to the next unsorted element

Worked trace:

List: [64, 34, 25, 12, 22]

• 64 → already sorted portion: [64]
• 34 → 34 < 64, insert before: [34, 64, 25, 12, 22]
• 25 → 25 < 64, 25 < 34, insert at start: [25, 34, 64, 12, 22]
• 12 → 12 < all, insert at start: [12, 25, 34, 64, 22]
• 22 → 22 > 12, 22 < 25, insert at position 1: [12, 22, 25, 34, 64]

Complexity: O(n²) worst case, but O(n) for nearly-sorted data — makes it practical in some real situations.

---

Merge Sort

Merge sort is a divide and conquer algorithm. It recursively splits the list in half, sorts each half, and merges the sorted halves together.

How it works:

1. If the list has 0 or 1 elements, it’s already sorted
2. Split the list into two halves
3. Recursively sort each half
4. Merge the two sorted halves

Worked trace:

List: [38, 27, 43, 3, 9, 82, 10]

Split phase:

[38, 27, 43, 3, 9, 82, 10]
[38, 27, 43]    [3, 9, 82, 10]
[38] [27, 43]   [3, 9] [82, 10]
     [27] [43]  [3] [9] [82] [10]

Merge phase:

[27] + [43] → [27, 43]
[38] + [27, 43] → [27, 38, 43]
[3] + [9] → [3, 9]
[82] + [10] → [10, 82]
[3, 9] + [10, 82] → [3, 9, 10, 82]
[27, 38, 43] + [3, 9, 10, 82] → [3, 9, 10, 27, 38, 43, 82]

Python:

def merge_sort(lst):
    if len(lst) <= 1:
        return lst
    mid = len(lst) // 2
    left = merge_sort(lst[:mid])
    right = merge_sort(lst[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

Complexity: O(n log n) — consistently efficient even for large datasets.

---

Complexity Comparison

Algorithm	Best case	Worst case	Space	Stable?
Linear search	O(1)	O(n)	O(1)	—
Binary search	O(1)	O(log n)	O(1)	—
Bubble sort	O(n)	O(n²)	O(1)	Yes
Insertion sort	O(n)	O(n²)	O(1)	Yes
Merge sort	O(n log n)	O(n log n)	O(n)	Yes

A Level note: For AQA 7517, you also need to know quicksort (average O(n log n)), Dijkstra’s shortest path (O(V² + E) with basic implementation), and A* search (heuristic-guided).

---

Exam Technique

Trace table questions

These ask you to complete a table showing the state of the list after each comparison or swap. Tips:

• Write every swap, not just the end of each pass
• Check how many elements the question says to trace (don’t do extra work)
• If you make a mistake, cross it out neatly — don’t use correction fluid

”State the advantages/disadvantages” questions

Bubble sort advantages: simple to understand, easy to implement, can detect a sorted list early with the optimised version Bubble sort disadvantages: inefficient (O(n²)), not suitable for large datasets

Merge sort advantages: efficient for large datasets (O(n log n)), consistent performance Merge sort disadvantages: requires extra memory (O(n)), more complex to implement

Binary search advantages: very fast (O(log n)) Binary search disadvantages: list must be sorted first; sorting takes time

---

Need help working through algorithm questions? Our revision platform has interactive trace tables and a full question bank covering algorithms for all major exam boards. Or book a session with Gareth for personalised algorithm practice.