Level:
Correct: 0
Incorrect: 0
Marks: 0/0
Exam Practice
Course:
Topics:
AQA GCSE Computer Science (Paper 1) Smart practice A mixed round aimed at your weak spots
Unit 1
3.1 Fundamentals of algorithms
Unit 2
3.2 Programming
Data types
Data types
Arithmetic operations in a programming language
Arithmetic operations, DIV and MOD
Relational operations in a programming language
Relational operations
Boolean operations in a programming language
Boolean operations in conditions
Data structures
Arrays and records
Input/output
Input and output
String handling operations in a programming language
String handling
Random number generation in a programming language
Random number generation
Structured programming and subroutines (procedures and functions)
Subroutines and structured programming
Avg
score:
–
Topics
done:
0/15

Merge sort and bubble sort

Practise 30 exam-style questions on Merge sort and bubble sort for AQA GCSE Computer Science (Paper 1). Write your answer as you would in the exam and get it marked in seconds against the mark scheme, point by point, with the Study Helper on hand if you get stuck.

  • 30 questions
  • 1–7 marks each
  • Instant marking
  • No sign-up needed
20 questions, marked as you go

Sample questions with model answers

Here are 4 of the questions in this topic, each with a model answer, an explanation of why it earns the marks and the mark scheme an examiner would use.

Question 1

1 mark

Which one of the following statements about a merge sort is true?

Choose your answer.

  • It needs extra memory to store the sub-lists
  • It can only sort lists with an even number of items
  • It swaps neighbouring items until a pass makes no swaps
  • It is slower than a bubble sort for large lists

Model answer

It needs extra memory to store the sub-lists

Explanation

A merge sort builds new sub-lists as it splits and merges, so it uses more memory than a bubble sort. It works on lists of any length, because an odd-length list just splits into unequal halves. Swapping neighbours until a pass makes no swaps describes a bubble sort, and a merge sort is faster, not slower, for large lists.

Mark scheme
  1. 1 mark

    It needs extra memory to store the sub-lists

    If more than one option is given, 0 marks. Mark is for AO1 (understanding).

Question 2

2 marks

Sam writes this pseudo-code to swap the two values in the array vals.

vals ← [6, 2]
vals[0] ← vals[1]
vals[1] ← vals[0]
OUTPUT vals[0]
OUTPUT vals[1]

State the output, and explain why the code does not swap the values.

Model answer

Output: 2 then 2.
vals[0] ← vals[1] copies 2 over the 6, so the 6 is lost before it can be copied into vals[1]. A temporary variable is needed:

temp ← vals[0]
vals[0] ← vals[1]
vals[1] ← temp

Explanation

An assignment replaces the old value, so after the first line both elements hold 2 and the second line just copies 2 onto itself. Saving one value in a temporary variable first is why bubble sort code always uses three lines to swap. This is a logic error: the code runs, but gives the wrong result.

Mark scheme
  1. 1 mark

    2 then 2 / 2, 2

    Both marks AO2 (apply).

  2. 1 mark

    the first assignment overwrites the 6 in vals[0] before it has been copied, so the 6 is lost / a temporary variable is needed to hold one value during the swap

Question 3

3 marks

During a merge sort, the two sorted sub-lists [3, 9, 14, 20] and [5, 6, 17, 25] are merged into one list.

Describe how these two sub-lists are merged, and state the merged list.

Model answer

Compare the first item of each sub-list: 3 and 5. 3 is smaller, so 3 goes into the new list. Then compare 9 and 5: 5 goes next. Keep comparing the first remaining item of each sub-list and moving the smaller one into the new list (9 v 6, 9 v 17, 14 v 17, 20 v 17, 20 v 25). When the first sub-list is empty, the rest of the second (25) is added to the end.
Merged list: 3, 5, 6, 9, 14, 17, 20, 25

Explanation

Because both sub-lists are already sorted, the smallest remaining item is always at the front of one of them, so only the two front items need comparing. Taking the smaller each time builds the merged list in order, and when one list runs out the rest of the other is already in order. This is why merging never needs a separate sort.

Mark scheme
  1. 1 mark

    the first items of the two sub-lists are compared (3 and 5) and the smaller one (3) is put into the new list

    All marks AO2 (apply). R. for marks 1 and 2 'the lists are joined together and then sorted'.

  2. 1 mark

    this is repeated, comparing the first remaining items of each sub-list (e.g. 9 and 5, so 5 goes next), until one sub-list is empty; then the rest of the other sub-list (25) is added to the end

    A. an answer that shows the comparisons in order (3/5, 9/5, 9/6, 9/17, 14/17, 20/17, 20/25) and then adds 25.

  3. 1 mark

    merged list: 3, 5, 6, 9, 14, 17, 20, 25

Question 4

5 marks

The first row of the table in the figure shows an array before a bubble sort starts to sort it into ascending order.

State the order of the array after every swap, giving one row of the table for each swap, in the order the swaps happen.

Trace table with five columns: [0], [1], [2], [3] and [4]. Columns [0] to [4] are grouped under the heading Array. Row 1: [0] = 31, [1] = 46, [2] = 18, [3] = 52, [4] = 27. Rows 2 to 8 are empty, for the student to complete.

Model answer

31, 18, 46, 52, 27
31, 18, 46, 27, 52
18, 31, 46, 27, 52
18, 31, 27, 46, 52
18, 27, 31, 46, 52

Explanation

Pass 1 swaps 46 and 18, then 52 and 27; pass 2 swaps 31 and 18, then 46 and 27; pass 3 swaps 31 and 27, and pass 4 makes no swaps. Each swap changes the order, so each needs its own row. Showing only the order at the end of each pass misses rows and is the most common way to lose marks.

Mark scheme
  1. 1 mark

    31, 18, 46, 52, 27

    All marks AO2 (apply). 1 mark for each correct row in the correct order. I. Blanks for values that have not changed, if the order is clear. I. The final sorted row written again at the end. Maximum 4 marks if any extra or incorrect rows are given. If only the order at the end of each pass is shown (31, 18, 46, 27, 52 / 18, 31, 27, 46, 52 / 18, 27, 31, 46, 52), award a maximum of 2 marks.

  2. 1 mark

    31, 18, 46, 27, 52

  3. 1 mark

    18, 31, 46, 27, 52

  4. 1 mark

    18, 31, 27, 46, 52

  5. 1 mark

    18, 27, 31, 46, 52

Ready to try the rest? Every answer you write is marked against the mark scheme, so you can see exactly where the marks are.

Study Helper Hints first, answers after you try

Stuck on this one? Ask for a hint and I’ll point you in the right direction, without giving the answer away. Once you’ve checked your answer, I’ll show you how the marks are awarded.