OCR GCSE Computer Science Computational thinking, algorithms and programming (02), June 2025: Question 3

9 marks · Medium difficulty · Short Answer

Demonstrate the steps of a merge sort, identify characteristics of sorting algorithms and arrays, and name and describe conditions for a linear search algorithm.

Practise this question

Question

Question 3 consists of three parts. Part (a) asks students to show the steps a merge sort would take to sort the list '2, 7, 3, 1, 9, 6, 5, 4' into ascending order within a large workspace. Part (b) presents three tick-box tables to complete statements about an insertion sort, bubble sort, and arrays. Part (c) outlines a searching algorithm that checks values sequentially and asks for its name and another condition that would cause it to stop.
Question text

(a) Show the steps that a merge sort would take to put the data set into ascending numerical order.

2, 7, 3, 1, 9, 6, 5, 4

6 [4]

(b) Tick (✓) one box in each table to complete the descriptions.

An insertion sort…

Tick (✓)

one

uses an array of numbers with a sorted part and unsorted part

picks out the middle value to begin with

merges arrays of numbers together

A bubble sort compares pairs of values and then:

Tick (✓)

one

always swaps them

swaps them if they are in the correct order

swaps them if they are in the incorrect order

A sorting algorithm can sort data in an array. An array:

Tick (✓)

one

is declared with a fixed length

stores multiple values that cannot be changed while the

program is running

can only be declared with a maximum of one-dimension (1D)

[3]

(c) An algorithm can be used to search for a value in an array. The algorithm follows these steps:

• compares the first value in the array to the value being searched for

• stops if the comparison is true

• moves to the next value in the array if the comparison if false.

(i) Give the name of the searching algorithm described.

… [1]

(ii) Identify one other condition that will cause the algorithm to stop.

… [1]

Mark scheme

Show the mark scheme Mark scheme for Question 3: (a) awards 4 marks for splitting into individual lists, sorting into sub-lists of size 2 ([2,7], [1,3], [6,9], [4,5]), lists of size 4 ([1,2,3,7], [4,5,6,9]), and fully merged list [1,2,3,4,5,6,7,9]. (b) awards 3 marks for ticking 'uses an array of numbers with a sorted part and unsorted part', 'swaps them if they are in the incorrect order', and 'is declared with a fixed length'. (c)(i) awards 1 mark for 'Linear search' and (c)(ii) awards 1 mark for 'End of list reached / checked every value'.

Question Answer Mark Guidance

3 (a) (i) • Split up into individual lists each of one item 4 Do not allow merging out of order and then

(divide stage) sorting for BP 3 or 4.

• [2,7] [1,3] [6,9] [4,5] (sorted lists of 2)

• [1, 2, 3, 7] [4, 5, 6, 9] (sorted lists of 4) Splitting can be done in multiple stages or all at

• [1, 2, 3, 4, 5, 6, 7, 9] after reasonable once. If no attempt at splitting up, assume initial list

attempt at merging from 4 to 8 is already split up and mark BP2, 3 and 4. If

splitting done incorrectly, do not give BP1 but allow

access to further points.

Do not accept sorted list for BP4 if no steps shown

or wrong algorithm used.

Brackets not needed around numbers – must be

reasonably clear numbers are in 2s, 4s, etc.

If candidate uses numbers other than the ones

given in the question or sorts into descending

order, penalise once then FT.

3 (b) • Uses an array of numbers with a sorted part 3 No mark if more than one box ticked per section.

and unsorted part (top )

• Swaps them if they are in the incorrect order

(bottom )

• Is declared with a fixed length (top )

3 (c) (i) • Linear search 1 Accept ”linear” by itself

Do not allow “linear sort”

3 (c) (ii) • End of list reached // gets to last value (and 1 Do not accept "value not found / value not in list”

not found) // checked every value (and value by itself. Must have idea of getting to the end or

not found) having checked the entire list.

How to answer it

Standard Searching and Sorting Algorithms

📌 What this question tests

This question assesses core algorithmic knowledge from OCR GCSE Computer Science (Component 2):

  • Merge Sort: Tracing the divide-and-conquer stages step-by-step (splitting down to 1-item sublists and merging in sorted order).
  • Algorithm Characteristics: Identifying how Insertion Sort and Bubble Sort operate, as well as the fundamental definition of an array.
  • Linear Search: Recognizing the sequential search algorithm and understanding both of its loop termination conditions.

Part (a): Trace a Merge Sort

4 Marks

📐 Step-by-Step Merge Sort Trace

Start data: 2, 7, 3, 1, 9, 6, 5, 4

Stage 1: Divide (Split until lists are size 1)

2 7 3 1
9 6 5 4
↓
2 7
3 1
9 6
5 4
↓
2
7
3
1
9
6
5
4

✔ Mark 1: All elements separated into individual sublists of 1 item

Stage 2: Combine & Sort (Merge pairs back together)

2 7
1 3
6 9
4 5

✔ Mark 2: Lists of size 2 formed, sorted internally: [2, 7], [1, 3], [6, 9], [4, 5]

↓
1 2 3 7
4 5 6 9

✔ Mark 3: Lists of size 4 formed, sorted internally: [1, 2, 3, 7], [4, 5, 6, 9]

↓
1 2 3 4 5 6 7 9

✔ Mark 4: Final combined sorted list: [1, 2, 3, 4, 5, 6, 7, 9]

❌ Common Errors in Merge Sort

  • Merging out of order then sorting: You cannot just smash [2, 7] and [3, 1] into [2, 7, 3, 1] and then swap them. The items must be merged directly in order.
  • Stopping before size 1: Forgetting to show the single-element lists loses the first dividing mark.
  • Skipping intermediate steps: Jumping from individual elements straight to the final list scores a maximum of 1 mark.

🧠 Exam Technique

  • Use square brackets or clear spaces so the examiner can tell where one sublist ends and another begins (e.g. [2, 7] [1, 3] ).
  • Keep the rows aligned clearly downwards to make the divide and conquer tree obvious.

Part (b): Algorithm & Data Structure Features

3 Marks (1 mark per table)

✅ Correct Options

1. An insertion sort...

uses an array of numbers with a sorted part and unsorted part ✔ (Tick)
picks out the middle value to begin with
merges arrays of numbers together

2. A bubble sort compares pairs of values and then:

always swaps them
swaps them if they are in the correct order
swaps them if they are in the incorrect order ✔ (Tick)

3. An array:

is declared with a fixed length ✔ (Tick)
stores multiple values that cannot be changed while running
can only be declared with a maximum of one-dimension (1D)

💡 Why the Distractors are Incorrect

  • Insertion Sort: Picking the middle value is part of a binary search. Merging arrays is part of a merge sort. Insertion sort always divides the data conceptually into a sorted section on the left and unsorted on the right.
  • Bubble Sort: It never swaps elements that are already ordered; it only swaps pairs when they are in the wrong order.
  • Arrays:
    • Arrays are static (fixed size upon declaration).
    • Elements can be updated while running (they are mutable).
    • Arrays can be multi-dimensional (e.g., 2D arrays like matrices or grids).
Examiner Rule: Exactly one tick per table. If more than one box is ticked in any table, that mark is immediately forfeited.

Part (c): Searching Algorithms

2 Marks total

(i) Identify Algorithm Name (1 Mark)

Answer: Linear search (or Linear )

❌ Do NOT write: Linear sort . The question explicitly asks for a searching algorithm.

(ii) Second Stopping Condition (1 Mark)

The first condition given was: stops if the comparison is true (item is found).

Answer: Any one of:

  • The end of the list/array is reached
  • Reaches the last item (and the value is not found)
  • Every value has been checked without finding the target

❌ Critical Trap on Part (c)(ii)

Do not just say "the value is not found" .

How does the computer actually know the value isn't there? It knows because the loop pointer has reached the end of the array. You must state the physical condition that halts the execution.

💡 Linear Search vs Binary Search Recall

  • Linear Search: Starts at item 0, checks sequential items one-by-one. Does not require sorted data.
  • Binary Search: Checks midpoint, discards half. Must have sorted data beforehand.

Topics

2.1 Algorithms · 2.2 Programming fundamentals · 2.1.3 Searching and sorting algorithms · 2.2.3 Additional programming techniques

Question and mark scheme from the OCR GCSE Computer Science examination, Computational thinking, algorithms and programming (02), June 2025. QuestionVault is an independent revision resource; questions remain the copyright of the awarding body.