AQA GCSE Computer Science Paper 1 (1B), June 2025: Question 6

10 marks · Medium difficulty · Short Answer

Demonstrate the execution of bubble sort and merge sort on an array of numbers, compare the two sorting algorithms, and explain why binary search is more efficient than linear search for a large sorted array.

Practise this question

Question

Question text

06 A series of numbers shown in Figure 6 are to be sorted into ascending order (from

smallest to largest).

Figure 6

45 23 78 55 49

06.1 A bubble sort algorithm has been developed to sort the numbers in Figure 6.

Fill in the table to show the steps involved in applying a bubble sort algorithm to sort

the numbers shown in Figure 6.

You should show the new order every time the order has changed.

[3 marks]

45 23 78 55 49

23 45 17 49 55 78

06.2 A programmer decides to use a merge sort algorithm to sort the same values shown

in Figure 6.

Complete the diagram to show how the merge part of the merge sort algorithm is

applied to Figure 6.

[3 marks]

06.3 State one advantage and one disadvantage of a bubble sort compared to a merge

sort.

[2 marks]

Advantage

Disadvantage

06.4 The programmer has an array of 2500 numbers, stored in ascending order (smallest

to largest).

The programmer needs to write a program to search for a value in the array.

Explain why a binary search is better than a linear search for this array.

[2 marks]

Mark scheme

Show the mark scheme

Total

Question Part Marking guidance

marks

06 1 3 marks for AO2 (apply) 3

1 mark for each correct change in correct order;

I. Blanks for repeated values.

Maximum 2 marks if grid not fully correct.

The correct sequence is:

45 23 78 55 49

23 45 78 55 49

23 45 55 78 49

23 45 55 49 78

23 45 49 55 78

If the response shows the sort completed in a single pass, as follows, then

award 1 mark;

45 23 78 55 49

23 45 55 49 78

23 45 49 55 78

Total

Question Part Marking guidance

marks

06 2 3 marks for AO2 (apply) 3

MP1: for correctly sorting pairs (Red Boxes);

MP2: for correctly leaving 1 element on its own after sorting pairs (Green

Boxes);

MP3: for correctly sorting 3 or 4 elements (Blue Boxes);

Maximum two marks if any errors

I. if the final row has been rewritten by the student

Example One (fully correct)

Example Two (fully correct)

Example Three (fully correct)

Question Part Total

Marking guidance

marks

06 3 2 marks for AO1 (understanding) 2

Advantage of bubble sort

Maximum of 1 mark from:

● Bubble sort is simpler to code // Algorithm requires fewer lines of

code;

● Bubble sort can be quicker to sort small lists/arrays;

A. Bubble sort will use less memory // bubble sort only requires one

additional memory location (whereas merge sort requires more than one) ;

Disadvantage of bubble sort

Maximum of 1 mark from:

● Bubble sort does not sort (large) lists/arrays as quickly as merge

sort;

● Bubble sort is less efficient;

NE. Answers that have not been qualified (e.g. bubble sort is simple).

Total

Question Part Marking guidance

marks

06 4 2 marks for AO2 (apply) 2

● A binary search is more efficient (on average) / takes less time (on

average) ;

a linear search would be less efficient (on average) because it

(potentially) must check all (2500) elements;

● (because) fewer comparisons will need to be made (on average) to

locate the search term;

(For this scenario) a binary search would (take at maximum 12

searches as it) halves the number of values each time;

How to answer it

Algorithms: Sorting and Searching Mastery Guide

AQA GCSE Computer Science • Paper 1 (Computational Thinking & Problem Solving) • Question 06

What This Question Tests

Bubble Sort Mechanics: Tracing individual comparison swaps in an array step-by-step.
Merge Sort Reconstruction: Understanding the combination (merge) phase of a divide-and-conquer algorithm.
Algorithm Evaluation: Comparing the trade-offs of Bubble Sort vs Merge Sort (complexity, implementation, memory).
Binary vs Linear Search Efficiency: Explaining why halving the search space of sorted data dramatically outperforms linear scans.

Part 06.1: Step-by-Step Bubble Sort Trace 3 Marks • AO2

Fill in the table showing the new order every time the order changes.

✅ Correct Table (Order After Each Swap)

Step / Swap	Col 1	Col 2	Col 3	Col 4	Col 5
Initial State	45	23	78	55	49
Swap 1 (Row 1)	23	45	78	55	49
Swap 2 (Row 2)	23	45	55	78	49
Swap 3 (Row 3)	23	45	55	49	78
Final (Given)	23	45	49	55	78

[1 mark] for each correct row in sequence.

🧠 Exam Technique: Trace Every Single Swap

Read the constraint: "show the new order every time the order has changed " means write a new line per individual swap, NOT just at the end of each pass!
Trace mechanically:
1. Compare 45 & 23 → 45 > 23, swap! → Row 1.
2. Compare 45 & 78 → no swap.
3. Compare 78 & 55 → 78 > 55, swap! → Row 2.
4. Compare 78 & 49 → 78 > 49, swap! → Row 3.

❌ Common Mistakes to Avoid

Writing only the end of Pass 1 and Pass 2: If you only showed the state after entire passes, the mark scheme caps you at a maximum of 1 mark.
Writing comparisons that didn't swap: Only write a new row when an actual swap occurs!

Part 06.2: Merge Sort - Rebuilding the List 3 Marks • AO2

Complete the diagram to show how the merge phase is applied to Figure 6.

LEVEL 0: INDIVIDUAL ELEMENTS (DIVIDED)

45 23 78 55 49

↓ (Merge adjacent pairs into sorted sublists)

LEVEL 1: MERGE PAIRS + CARRY SINGLETON

[ 23 | 45 ] [ 55 | 78 ] [ 49 ]

↓ (Merge two 2-element lists together)

LEVEL 2: MERGE 4 ELEMENTS (OR 3 ELEMENTS)

[ 23 | 45 | 55 | 78 ] [ 49 ]

↓ (Final merge)

FINAL LEVEL (PRE-PRINTED ON EXAM PAPER)

[ 23 | 45 | 49 | 55 | 78 ]

✅ Mark Breakdown (How Marks Are Given)

MP1 [1 mark]: Correctly sorting pairs into 2-item lists (e.g. [23, 45] and [55, 78] ).
MP2 [1 mark]: Correctly leaving 1 element on its own after sorting pairs (e.g. [49] kept untouched).
MP3 [1 mark]: Correctly merging 3 or 4 elements into a sorted list (e.g. [23, 45, 55, 78] ).

🧠 Alternative Valid Structures

The examiners allow you to pair elements from the right or left:

Alternative A: Leave 45 on its own first, then merge pairs [23, 78] and [49, 55] . Next merge into [23, 49, 55, 78] .
Alternative B: At level 2, merge [55, 78] with [49] to create [49, 55, 78] alongside [23, 45] .

Part 06.3: Comparing Bubble Sort & Merge Sort 2 Marks • AO1

State one advantage and one disadvantage of a bubble sort compared to a merge sort.

✅ Accepted Answers

Advantage (1 Mark - choose one):

Simpler to code / implement (fewer lines of code).
Can be faster for small lists or nearly-sorted lists.
Uses less memory / works in-place (merge sort requires extra temporary memory space).

Disadvantage (1 Mark - choose one):

Much slower / less efficient on large lists.
Time complexity is worse (O(n²) compared to merge sort's O(n log n)).

❌ Examiner Pitfall: Unqualified Statements

"Bubble sort is simple" / "Bubble sort is easy": ❌ 0 marks! You MUST qualify what makes it simple (e.g. "simpler to write as code" or "easier to program").
"Bubble sort is slow": ❌ You must explicitly compare it: "Bubble sort takes longer to sort large lists than merge sort."

Part 06.4: Binary Search vs Linear Search 2 Marks • AO2

An array has 2500 sorted numbers. Explain why binary search is better than linear search.

✅ Model 2-Mark Answer

"A binary search is significantly more efficient / takes less time than a linear search on average [1 mark], because it halves the search space each time, requiring far fewer comparisons (a maximum of 12 comparisons) compared to linear search which could take up to 2500 comparisons [1 mark]."

📐 Mathematical Comparison

Linear Search (Worst Case):
Checks every element one by one = 2,500 comparisons.
Binary Search (Worst Case):
Halves the array each step:
log₂(2500) ≈ 11.28 → Maximum of 12 comparisons!
(2500 → 1250 → 625 → 312 → 156 → 78 → 39 → 19 → 9 → 4 → 2 → 1).

Mark Scheme Rules: MP1 awarded for stating that binary search is more efficient / takes less time (or linear search is less efficient because it may check all 2500 items). MP2 awarded for justifying with fewer comparisons / halving the data each step / citing max 12 comparisons.

Topics

3.1 Fundamentals of algorithms · 3.1.3 Searching algorithms · 3.1.4 Sorting algorithms

Question and mark scheme from the AQA GCSE Computer Science examination, Paper 1 (1B), June 2025. QuestionVault is an independent revision resource; questions remain the copyright of the awarding body.