GCSEPaper 2AlgorithmsSearching and sorting algorithms
2.1.3

Searching and sorting algorithms

Steps of binary and linear search plus bubble, merge and insertion sort.

Learning Objectives

  • 1Understand the main steps of linear search, binary search, bubble sort, merge sort and insertion sort
  • 2Understand any pre-requisites each algorithm needs, such as a sorted list
  • 3Apply each algorithm to a given data set by hand
  • 4Identify which algorithm is shown, given its code, pseudocode or Exam Reference Language

Searching and sorting algorithms

A searching algorithm finds a specific value in a list. A sorting algorithm puts a list into order. You need to know two searching algorithms (linear and binary search) and three sorting algorithms (bubble, merge and insertion sort). You do not need to memorise the exact code for these, you need to understand the steps and be able to apply them to a data set by hand.
You are required to know two standard searching algorithms (linear search, binary search) and three standard sorting algorithms (bubble sort, merge sort, insertion sort). For each, you should understand its main steps, any pre-requisites it needs, and be able to apply it to a data set by hand, or identify which algorithm a piece of given code represents. You are not required to remember or reproduce the code, pseudocode or Exam Reference Language for these algorithms from memory, it will always be given to you if needed.
The specification distinguishes between understanding and applying an algorithm and memorising its implementation: you must be able to trace an algorithm's execution on a given data set, recognise it from given code/pseudocode/ERL, and describe its behaviour and pre-requisites, but you are explicitly not required to write these five algorithms entirely from memory.

Linear search

Linear search checks each item in a list one by one, from the start, until it finds the target or reaches the end. It works on any list, sorted or not, but can be slow for large lists.
Linear search starts at the first item and checks each item in turn, comparing it to the target value, until either the target is found (its index is returned) or the end of the list is reached (meaning the target is not present). It works on any list, sorted or unsorted, is simple to implement, but can be slow for large lists, especially if the target is near the end or missing entirely.
Linear search has no pre-requisite, it works correctly on both sorted and unsorted data, which is its main advantage over binary search. The precise stopping condition matters: the algorithm stops either when the target is found, or when the end of the list has been reached without finding it, a vague "when the value is not found" is imprecise, since that is the outcome being tested, not the condition itself.
Python· Linear search: return the index of target, or -1 if not found
def linear_search(data, target):
    for i in range(len(data)):
        if data[i] == target:
            return i
    return -1
OCR ERL· Linear search: return the index of target, or -1 if not found
function linearSearch(data, size, target)
    for i = 0 to size - 1
        if data[i] == target then
            return i
        endif
    next i
    return -1
endfunction

Binary search

Binary search only works on a sorted list. It repeatedly looks at the middle item and discards half the list each time, which makes it much faster than linear search for large lists.
Binary search requires the list to already be sorted, this is its pre-requisite. It compares the target to the middle item: if they match, the search is done; if the target is smaller, the search continues on the left half; if larger, it continues on the right half. This "divide and conquer" approach repeats, halving the search range each time, until the item is found or the range has no items left.
Binary search's pre-requisite (a sorted list) is essential, since its logic relies on being able to discard half the remaining data based on a single comparison with the midpoint. This makes it significantly faster than linear search on large, sorted lists (logarithmic vs linear time), at the cost of more complex logic and the overhead of sorting the list first if it isn't already sorted.
Binary search for 23Index 0Index 1Index 2Index 3Index 4Index 5Index 6Index 7Step 1Middle item is 12258121623385612 is smaller than 23, so throw away 12 and everything to its leftStep 2Middle of the rest is 232581216233856Found at index 5Each step throws away half of whatever is left.This only works because the list is already sorted.
Python· Binary search: return the index of target in a sorted list, or -1
def binary_search(data, target):
    low = 0
    high = len(data) - 1
    while low <= high:
        mid = (low + high) // 2
        if data[mid] == target:
            return mid
        elif data[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1
OCR ERL· Binary search: return the index of target in a sorted list, or -1
function binarySearch(data, size, target)
    low = 0
    high = size - 1
    while low <= high
        mid = (low + high) DIV 2
        if data[mid] == target then
            return mid
        elseif data[mid] < target then
            low = mid + 1
        else
            high = mid - 1
        endif
    endwhile
    return -1
endfunction

Bubble sort

Bubble sort repeatedly compares two neighbouring items and swaps them if they are in the wrong order. It keeps making passes through the list until a full pass happens with no swaps, meaning the list is sorted.
Bubble sort makes repeated 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 unsorted item "bubbles up" to its correct position at the end, so each subsequent pass needs one fewer comparison. The algorithm stops once a full pass is made with no swaps.
Bubble sort is simple to implement but inefficient for large data sets, since it may require many passes, each comparing most of the list. One optimisation is that each pass guarantees the next-largest item is placed correctly, so the comparison range shrinks by one each pass. A final pass with zero swaps confirms the list is sorted.
Python· Bubble sort: sort data into ascending order
def bubble_sort(data):
    n = len(data)
    for i in range(n - 1):
        for j in range(n - 1 - i):
            if data[j] > data[j + 1]:
                data[j], data[j + 1] = data[j + 1], data[j]
    return data
OCR ERL· Bubble sort: sort data into ascending order
procedure bubbleSort(data, size)
    for i = 0 to size - 2
        for j = 0 to size - 2 - i
            if data[j] > data[j + 1] then
                temp = data[j]
                data[j] = data[j + 1]
                data[j + 1] = temp
            endif
        next j
    next i
endprocedure

Merge sort

Merge sort repeatedly splits the list in half until every sub-list has just one item, then merges those sub-lists back together in the correct order. It is the merging step that actually does the sorting.
Merge sort is a "divide and conquer" algorithm. First it repeatedly divides the list in half until each sub-list contains only one item (a single item is always "sorted"). Then it merges the sub-lists back together in pairs, always comparing the front of each sub-list and taking the smaller item first, so every list produced during merging is already in order. This continues until one fully sorted list remains.
It is critical that the merge step itself performs the sort, at every stage of merging, the resulting list must be in order, built by comparing the front elements of each sub-list and always taking the smaller. A common and serious misconception is to simply append (concatenate) sub-lists together into one unsorted list and then sort that, this is not merge sort and does not demonstrate understanding of the algorithm. Merge sort trades bubble sort's simplicity for much better performance on large data sets, at the cost of using more memory for the sub-lists it creates.
Merge sortDivideKeep halvingMergeSmallest first62716271627126171267SortedEach merge compares the front item of the two lists and takes the smaller one, until both lists are empty.

Insertion sort

Insertion sort builds up a sorted list one item at a time. It looks at the next item and inserts it into its correct position among the items already sorted so far.
Insertion sort starts from the second item in the list. Each item in turn is compared to the items before it (which are already sorted), and inserted into its correct position, shifting later items along if needed. This repeats until every item has been inserted into its correct place.
Points examiners credit for distinguishing insertion sort from bubble sort: it completes in one pass through the array (rather than repeated passes), each value is moved into its correct position once, items are shifted along to make room, and the start of the array becomes sorted first. Insertion sort is simple to implement and particularly efficient for small or nearly-sorted data sets, since few shifts are needed when data is already close to sorted order. It becomes inefficient for large, randomly-ordered data sets compared to merge sort, since many shifts may be required for each item inserted.
Python· Insertion sort: sort data into ascending order
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 = j - 1
        data[j + 1] = key
    return data
OCR ERL· Insertion sort: sort data into ascending order
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]
            j = j - 1
        endwhile
        data[j + 1] = key
    next i
endprocedure

Exam Phrasing: Use These Exact Phrases

  • ✓Linear search checks every item in order, from the start, until the target is found or the list ends
  • ✓Binary search only works on a sorted list, and repeatedly discards half the remaining data
  • ✓Bubble sort repeatedly compares and swaps adjacent items until no swaps are needed
  • ✓Merge sort splits the list into single items, then merges them back together in order
  • ✓Insertion sort inserts each item into its correct position among the items already sorted
  • 💡You don't need to memorise the exact code for these algorithms, focus on understanding the steps well enough to apply them by hand to a data set, or identify the algorithm from given code.
  • 💡State pre-requisites precisely, binary search requires a sorted list, this is a common, easy mark.
  • 💡Describing binary search, do not start with "split the list in half", examiners are told that is incorrect as a first step and earns nothing. The first step is: select the middle item and check whether it equals the target. "Compare it" on its own is also not enough, say you check for a match.
  • 💡For the end of a binary search, say it repeats until the value is found or the remaining list is down to 1 or 0 items. "Until the number is not in the list" is not enough, you have to say how you know that.
  • 💡For merge sort, always show the divide stage (splitting into single items) AND the merge stage (comparing and combining in order), never just append sub-lists and sort them afterwards.
  • 💡For linear search, the precise stopping condition is: the target is found, OR the end of the list is reached without finding it.
  • 💡When applying an algorithm to a data set by hand, show your working clearly, examiners can award partial credit for a correct method even if the final answer has a small error.

Wrong:

Merge sort: simply append (concatenate) the sub-lists together, then sort the combined list

Right:

Merge sort: merge the sub-lists together by comparing their front items and always taking the smaller one first, so the result is already in order

Why it matters: Examiners specifically flagged this as a common, serious misconception, appending then sorting is not merge sort and receives no credit for the merge step.

Wrong:

Binary search works on any list

Right:

Binary search only works on a list that is already sorted

Why it matters: Its logic (discarding half the list based on comparing to the middle) only works correctly if the data is in order.

Wrong:

An array can grow or shrink in size, just like a list

Right:

An array is a fixed-length, static data structure, unlike a dynamic list which can be appended to

Why it matters: Examiners noted candidates using Python (where lists are dynamic) sometimes incorrectly described arrays as flexible in size.

Question:

Apply bubble sort to sort the list [5, 1, 4, 2] into ascending order. Show the list after each pass. [4]

💡 Attempt this before revealing the answer, practice makes perfect!

Model Answer:

Pass 1: compare 5&1, swap → [1,5,4,2]. Compare 5&4, swap → [1,4,5,2]. Compare 5&2, swap → [1,4,2,5]. Pass 2 (one fewer comparison needed, since 5 is already in its final position): compare 1&4, no swap. Compare 4&2, swap → [1,2,4,5]. Pass 3 (one comparison only): compare 1&2, no swap, so the list [1,2,4,5] is confirmed sorted.

Mark Scheme:

  • 1Correct list after pass 1: [1, 4, 2, 5]
  • 2Correct list after pass 2: [1, 2, 4, 5]
  • 3Recognises the list is now sorted (a final pass with no swaps confirms this)
  • 4Shows adjacent comparisons and swaps correctly throughout, in the correct order

Tap a card to flip it. Use the arrow keys to move and space to flip.

Known 0 Still learning 0
1 / 12

Exam-style questions. Have a go, then reveal the mark scheme to check your answer.

1.State the pre-requisite that binary search requires, and explain why it is needed.

[2]

2.A candidate sorts [4, 2, 6, 1] using merge sort by writing [4, 2] and [6, 1] as two lists, then joining them to get [4, 2, 6, 1], then separately sorting this combined list. Explain why this is not a correct demonstration of merge sort.

[2]

3.Apply linear search to find the value 9 in the list [4, 8, 9, 2, 6]. State the index it would be found at, and explain why linear search would need to check fewer items than if it were searching for 6.

[3]

4.You are given the code below. Identify which sorting algorithm it represents, and justify your answer using a feature of the code.

[3]
Python· Identify this algorithm
for i in range(len(data) - 1):
    for j in range(len(data) - 1 - i):
        if data[j] > data[j + 1]:
            data[j], data[j + 1] = data[j + 1], data[j]
OCR ERL· Identify this algorithm
for i = 0 to size - 2
    for j = 0 to size - 2 - i
        if data[j] > data[j + 1] then
            temp = data[j]
            data[j] = data[j + 1]
            data[j + 1] = temp
        endif
    next j
next i

5.Apply insertion sort to the list [7, 3, 5, 1]. Show the list after each item has been inserted into its correct position.

[4]

6.Compare linear search and binary search, and explain when each would be the appropriate choice.

[6]
2025Question paperMark schemeExaminers' report
2024Question paperMark schemeExaminers' report
2023Question paperMark schemeExaminers' report
2022Question paperMark schemeExaminers' report

The examiners' reports are the most useful and least read of the three: they say what candidates actually got wrong each year. All files are hosted by OCR.

Past-paper questions grouped by topic

The same OCR questions, sorted by topic rather than by year (via Physics & Maths Tutor).

2025
Paper 2

A common and repeated misconception was that merge sort merges sub-lists together by simply appending one to the other (creating an unsorted list) and then sorting that combined list. In real merge sort, every list at every stage of merging is already in order, it is the process of merging (comparing and taking the smaller front item each time) that performs the sort. Where candidates showed this misconception, the relevant mark was not given.

Paper 2

When identifying the stopping condition for linear search, many candidates responded "when the value is not found", which is imprecise since that is the outcome, not the condition. The technically correct condition is when the end of the list is reached without finding the value, though answers referring to reaching the end of the list or having checked every item were also accepted.

Paper 2

Fewer candidates than expected could correctly identify that an array is defined by a fixed length (a static structure), likely because Python, the most commonly used language, supports dynamic lists by default rather than fixed-size arrays. Candidates should be clear that an array's size is fixed once declared, unlike a list which can grow.

Previous

Designing, creating and refining algorithms

Next

Programming fundamentals