Sorting algorithms: bubble, merge and insertion sort – GCSE Computer Science exam questions with mark scheme

1Grade 4–54 marks

A bubble sort is used to put this list into ascending order.

[6, 2, 9, 1, 5]

(a) Show the list after the first pass. [2]

(b) Show the list after the second pass. [1]

(a) 9 has moved to the end(1)
(a) Completely correct: [2, 6, 1, 5, 9](1)
(b) [2, 1, 5, 6, 9](1)
(c) A complete pass is made with no swaps; allow: when the swapped flag is still false at the end of a pass; allow: after n − 1 (here 4) passes have been made(1)
Answer: (a) [2, 6, 1, 5, 9]; (b) [2, 1, 5, 6, 9]; (c) a pass with no swaps
Examiner tip: One pass compares every adjacent pair once. Don't show the list after a single swap and call that a pass.

2Grade 6–74 marks

Show how a merge sort would sort this list into ascending order.

[38, 27, 43, 3, 9, 82, 10, 16]

[4]

Splits the list repeatedly until every item is in a list of its own (8 lists of 1)(1)
Merges into pairs: [27, 38] [3, 43] [9, 82] [10, 16](1)
Merges into fours: [3, 27, 38, 43] [9, 10, 16, 82](1)
Final merge: [3, 9, 10, 16, 27, 38, 43, 82](1)
Answer: [3, 9, 10, 16, 27, 38, 43, 82]
Examiner tip: Show the full split down to single items before you start merging. Examiners give a mark for that step.

3Grade 6–74 marks

An insertion sort is used to put these names into alphabetical order.

["Mo", "Ali", "Tia", "Ben", "Cat"]

Show the list after each pass of the insertion sort. [4]

Pass 1: [Ali, Mo, Tia, Ben, Cat](1)
Pass 2: [Ali, Mo, Tia, Ben, Cat] (Tia is already in place, no change)(1)
Pass 3: [Ali, Ben, Mo, Tia, Cat](1)
Pass 4: [Ali, Ben, Cat, Mo, Tia](1)
Answer: [Ali, Mo, Tia, Ben, Cat] → [Ali, Mo, Tia, Ben, Cat] → [Ali, Ben, Mo, Tia, Cat] → [Ali, Ben, Cat, Mo, Tia]
Examiner tip: Show the pass where nothing moves (Tia) as well. Missing it out loses a mark.

4Grade 6–74 marks

A program needs to sort a list of 50 000 customer records.

Compare merge sort and bubble sort for this task. [4]

Merge sort is more efficient / quicker than bubble sort for a large list such as 50 000 records(1)
…because merge sort (divide and conquer) makes far fewer comparisons, while bubble sort makes repeated passes, each comparing up to 49 999 adjacent pairs; allow: bubble sort's time grows much faster as the list gets bigger(1)
Any one from: bubble sort is simpler to code / understand; bubble sort sorts in place so needs little extra memory; bubble sort can stop early (no swaps) if the list is already (nearly) sorted(1)
Any one further point from: merge sort needs extra memory to hold the sub-lists; merge sort is harder to code (often recursive); a second different point from the bubble sort list above. Do not credit the same idea twice (e.g. 'bubble sort uses less memory' and 'merge sort uses more memory' = one point)(1)
Answer: Merge sort is much faster on 50 000 records because it makes far fewer comparisons, but it needs extra memory and is harder to code. Bubble sort is simpler, sorts in place and can stop early on a nearly sorted list, but is very slow on a large list.
Examiner tip: A compare question needs points about both algorithms, ideally linked with 'whereas'. Writing the same point twice from each side (e.g. less memory / more memory) only earns one mark.

Book a free introductory session and we'll find exactly which step is costing you.