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

10 marks · Medium difficulty · Short Answer

Demonstrate bubble sort and merge sort on a list of numbers, compare the two sorting algorithms, and explain why binary search is preferable to linear search for a large sorted array.

Practise this question

Question

Question 6 consists of four parts based on sorting and searching algorithms. Figure 6 shows an array of five numbers: 45, 23, 78, 55, 49. In part 6.1, a table with five columns and five rows is provided to show each step of a bubble sort where the order changes. In part 6.2, a large empty box between the initial five single-element boxes and the final sorted array of five boxes is provided to complete the merging phase of merge sort. Part 6.3 asks to state one advantage and one disadvantage of bubble sort compared to merge sort. Part 6.4 presents an array of 2500 numbers in ascending order and asks to explain why binary search is better than linear search for this array.
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 Mark scheme for Question 6: Part 6.1 awards up to 3 marks for writing the correct row-by-row sequence of numbers whenever a swap occurs in bubble sort: (23, 45, 78, 55, 49), then (23, 45, 55, 78, 49), then (23, 45, 55, 49, 78). Part 6.2 awards 3 marks for correctly showing the merge tree steps (sorting pairs, handling the single element, then combining into sorted sub-lists). Part 6.3 gives 1 mark for an advantage of bubble sort (e.g. simpler to code, uses less memory) and 1 mark for a disadvantage (less efficient / slower for large lists). Part 6.4 awards 2 marks for explaining that binary search is faster/more efficient on average as it halves the search space each time, needing far fewer comparisons than linear search which could check all 2500 items.

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

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

Sorting & Searching Algorithms Guide

AQA GCSE Computer Science • Paper 1 / Algorithms

📋 What this question tests

This question assesses your understanding of fundamental searching and sorting algorithms:

  • Bubble Sort: Tracing the algorithm step-by-step and recording state changes after every swap.
  • Merge Sort: Reconstructing the merge (combine) phase of a divide-and-conquer algorithm.
  • Algorithm Evaluation: Comparing the trade-offs (time complexity, memory usage, implementation complexity) between Bubble Sort and Merge Sort.
  • Searching Comparison: Explaining why Binary Search outperforms Linear Search on large, sorted datasets.

Question 06.1: Tracing a Bubble Sort

Fill in the trace table showing order changes [3 marks]

✅ Correct Answer

The prompt specifies: "show the new order every time the order has changed".

Initial4523785549
Swap 1 23 45 78 55 49
Swap 2 23 45 55 78 49
Swap 3 23 45 55 49 78
Given final 23 45 49 55 78
Mark Scheme:
• 1 mark for each correctly completed row in the exact order.
• Maximum 2 marks if the grid contains errors.

📐 Step-by-Step Logic (Pass 1)

  1. Compare index 0 & 1 (45 and 23): 45 > 23, so swap.
    List becomes: [23, 45, 78, 55, 49] (Row 1)
  2. Compare index 1 & 2 (45 and 78): 45 < 78, already in order. No swap.
  3. Compare index 2 & 3 (78 and 55): 78 > 55, so swap.
    List becomes: [23, 45, 55, 78, 49] (Row 2)
  4. Compare index 3 & 4 (78 and 49): 78 > 49, so swap.
    List becomes: [23, 45, 55, 49, 78] (Row 3)
  5. Notice: 78 has now "bubbled" to the end! Pass 2 then swaps 55 and 49 to reach the pre-printed final state.

🧠 Exam Technique: "Every time the order changes"

Read the rubric carefully! A bubble sort question can ask for:

  • The state after each individual swap (like this question).
  • The state after each complete pass.

Because there were exactly 3 blank rows provided before the final list, this gives you a clue that exactly 3 swaps occur during Pass 1.

❌ Common Errors

  • Showing only complete passes: Writing the result of Pass 1 on Row 1, Pass 2 on Row 2, etc. (Earns only 1 mark maximum).
  • Writing comparisons that don't swap: Do not add a row if two items were compared but stayed in the same position.

Question 06.2: Merge Sort Diagram

Complete the merge phase of the Merge Sort [3 marks]

✅ Model Solution (Standard Grouping)

Starting single items: [45] [23] [78] [55] [49]

Stage 1: Merge into sorted sub-lists of pairs

23 | 45 55 | 78 49
↓

Stage 2: Merge pairs into larger sorted sub-list

23 | 45 | 55 | 78 49
↓

Final Row (Pre-printed):

23 | 45 | 49 | 55 | 78

💡 Mark Scheme Breakdown

  • MP1 (1 mark): Correctly sorting pairs (e.g., [23, 45] and [55, 78] ).
  • MP2 (1 mark): Leaving the remaining single element on its own after merging pairs (e.g., [49] brought down).
  • MP3 (1 mark): Correctly sorting into a merged list of 3 or 4 elements before the final list.
Alternative groupings are fully accepted: For example, leaving [45] alone first and pairing [23, 78] & [49, 55] is equally valid!

❌ Examiner Trap to Avoid

Do NOT redraw the split (divide) stage! The single individual boxes were already provided at the top. The question strictly asked for the merge part. Drawing the divide phase wastes space and time.

Question 06.3: Comparing Bubble Sort vs Merge Sort

State one advantage and one disadvantage of a bubble sort [2 marks]

✅ Model Answers

Advantage (1 mark):

  • "Bubble sort is simpler to code and implement (fewer lines of code)." OR
  • "It uses less memory because it sorts in-place (merge sort requires additional auxiliary memory for sub-lists)." OR
  • "It can be faster for small lists or lists that are already nearly sorted."

Disadvantage (1 mark):

  • "It is much slower / less efficient than merge sort when sorting large lists."

❌ Common Errors & Examiner Notes

  • Vague answers: Simply writing "Bubble sort is simple" scores 0 marks. You must qualify it (e.g., "simple to program / code").
  • Forgetting to compare: Ensure you are highlighting advantages/disadvantages relative to merge sort as requested by the prompt.

Question 06.4: Binary Search vs Linear Search

Explain why a binary search is better for an array of 2500 sorted numbers [2 marks]

✅ Model Answer [2 marks]

"A binary search is much more efficient and faster on average [1 mark] because it repeatedly halves the search space, meaning far fewer comparisons are needed (a maximum of 12 comparisons) compared to linear search which may need up to 2500 comparisons [1 mark] ."

📐 The Math Behind the Efficiency

  • Linear Search worst-case: Must check every single item = 2,500 comparisons.
  • Binary Search worst-case: Halves the dataset each step:
    2500 → 1250 → 625 → 313 → 157 → 79 → 40 → 20 → 10 → 5 → 3 → 2 → 1
    Takes at most 12 comparisons (since 2¹¹ = 2048 and 2¹² = 4096).

🧠 How to Get Both Marks

  • Mark 1: State that binary search is more efficient / takes less time / performs fewer comparisons (or that linear search might have to inspect all 2,500 items).
  • Mark 2: Explain why: state that binary search halves the list each time or compare the number of comparisons (12 vs 2500).

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 (1A), June 2025. QuestionVault is an independent revision resource; questions remain the copyright of the awarding body.