OCR GCSE Computer Science June 2022 Paper 2, Question 3(a): showing a merge sort
OCR J277/02 June 2022, Question 3(a): show each step of a merge sort on eight positive and negative numbers, from single items to pairs, fours and the final sorted list. The three marks explained, with a merge sort that prints every stage.
Question 3(a) of the OCR GCSE Computer Science Paper 2 sat on 27 May 2022 (J277/02) gives you eight numbers already split into single items and asks you to finish the merge sort, showing each step. It is worth 3 marks: one for each level of merging.
We do not copy the exam paper here. Open it beside this page: OCR June 2022 J277/02 question paper (PDF). When you have finished, check the mark scheme too.
The question in short
The list is 45, 12, -99, 100, -13, 0, 17, -27. The splitting has been done. You do the merging, in ascending order.
Work it through
Merge neighbours, left to right. Each merge takes two sorted lists and builds one sorted list by repeatedly taking the smaller of the two front items.
Step 1: merge into pairs.
| 12, 45 | -99, 100 | -13, 0 | -27, 17 |
|---|---|---|---|
Step 2: merge the pairs into fours.
| -99, 12, 45, 100 | -27, -13, 0, 17 |
|---|---|
To merge 12, 45 with -99, 100: compare 12 and -99, take -99. Compare 12 and 100, take 12. Compare 45 and 100, take 45. Then 100 is left.
Step 3: merge the fours into one list.
| -99, -27, -13, 0, 12, 17, 45, 100 |
|---|
One mark for each step. The groups must clearly be the right size at each stage.
Where the marks are lost
- Getting negative numbers the wrong way round. -99 is smaller than -27. On a number line it is further left. The negative numbers are what make this list harder.
- Jumping to the sorted list. The final list alone gets nothing. The question says show each step, and the third mark is for merging the fours, not for the answer.
- Merging the wrong neighbours. 45 pairs with 12, the item next to it. You do not get to choose partners.
- Merging and then sorting. Putting two lists together unsorted and then sorting them in place is not a merge, and the mark scheme refuses it.
Run it
A merge sort in Python that prints the list of lists after every level of merging, so its output is the answer.
The program
from bugbot import *
connect()
numbers = [45, 12, -99, 100, -13, 0, 17, -27]
def merge(left, right):
result = []
while len(left) > 0 and len(right) > 0:
if left[0] <= right[0]:
result.append(left.pop(0))
else:
result.append(right.pop(0))
return result + left + right
lists = [[n] for n in numbers]
print(lists)
while len(lists) > 1:
merged = []
for i in range(0, len(lists), 2):
if i + 1 < len(lists):
merged.append(merge(lists[i], lists[i + 1]))
else:
merged.append(lists[i])
lists = merged
print(lists)
Questions
What is the answer to OCR J277 June 2022 Paper 2 Question 3(a)?
Pairs: 12 45, -99 100, -13 0, -27 17. Fours: -99 12 45 100 and -27 -13 0 17. Final list: -99 -27 -13 0 12 17 45 100.
How does a merge sort work?
It splits the list in half again and again until every list holds one item. Then it merges neighbouring lists in order, pair by pair, until one sorted list is left.
How do you merge two sorted lists?
Compare the first item of each list and move the smaller one to the new list. Repeat until one list is empty, then add what is left of the other.
More from this paper
- Question 3(b), (c): Describe a binary search, and a linear search for a number that is not there 6 marks
Every OCR J277 question we have worked · Guide: Big O notation explained
Learn it step by step
- F5.9 Merge sort and comparing algorithms Algorithms
This is our own explanation of a published exam question. It is not written or endorsed by OCR, and the question paper and mark scheme remain OCR's copyright. Read them on OCR's site with the links on this page.