Level:
Correct: 0
Incorrect: 0
Marks: 0/0
Exam Practice
Course:
Topics:
OCR GCSE Computer Science (Paper 2) Smart practice A mixed round aimed at your weak spots
Unit 1
Algorithms
Unit 2
Programming fundamentals
Unit 3
Producing robust programs
Unit 4
Boolean logic
Unit 5
Programming languages and IDEs
Unit 6
Practical programming (Section B)
Avg
score:
–
Topics
done:
0/31

Merge sort and insertion sort

Practise 32 exam-style questions on Merge sort and insertion sort for OCR GCSE Computer Science (Paper 2). 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.

  • 32 questions
  • 1–6 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

2 marks

A merge sort is used to sort a list of 16 items.

State how many stages of splitting are needed to split the list into single items, and how many stages of merging are then needed to produce one sorted list.

Model answer

Splitting: 16 items, then lists of 8, 4, 2 and 1, so 4 stages.
Merging: lists of 1, then 2, 4, 8 and 16, so 4 stages.

Explanation

Each splitting stage halves the size of the lists, and each merging stage doubles it. 16 can be halved 4 times before reaching 1, so there are 4 stages each way. Doubling the length of the list adds only one more stage, which is why merge sort copes so well with large lists.

Mark scheme
  1. 1 mark

    4 stages of splitting

    16, 8, 4, 2, 1

  2. 1 mark

    4 stages of merging

    1, 2, 4, 8, 16

Question 2

3 marks

The code below is part of a sorting algorithm. The arrays left and right each hold 4 numbers in ascending order, and result is an array of 8 elements.

i = 0
j = 0
k = 0
while i < 4 AND j < 4
    if left[i] <= right[j] then
        result[k] = left[i]
        i = i + 1
    else
        result[k] = right[j]
        j = j + 1
    endif
    k = k + 1
endwhile
while i < 4
    result[k] = left[i]
    i = i + 1
    k = k + 1
endwhile
while j < 4
    result[k] = right[j]
    j = j + 1
    k = k + 1
endwhile

State the name of the sorting algorithm that this code is part of, and explain the purpose of the last two while loops.

Model answer

It is part of a merge sort (it merges two sorted lists). The first while loop stops as soon as one of the lists has been used up. The last two loops then copy whatever is left in the other list (left or right) into the end of result. Only one of them actually runs. No comparisons are needed, because the leftover items are already in order and are all larger than (or equal to) everything already in result.

Explanation

This is the merge step: compare the front items, copy the smaller, and move on. When one list runs out, the rest of the other list can be copied straight across. Recognising this compare-and-copy pattern, with three index variables, is how you identify merge sort code.

Mark scheme
  1. 1 mark

    merge sort

  2. 1 mark

    the first loop stops when all the items of one list have been used; the last two loops copy the remaining items of the other list into result

    accept 'only one of them will run' as part of a correct explanation

  3. 1 mark

    the remaining items need no comparisons, because they are already in order and are all at least as large as the items already in result

Question 3

4 marks

Describe how a merge sort sorts a list of numbers into ascending order.

Model answer

The merge sort splits the list in half, then splits each half in half again, and keeps going until every sub-list contains just one item. It then merges pairs of sub-lists: it compares the first items of the two sub-lists, moves the smaller one into a new list, and repeats until both are used up, so each merged list is in order. The merging is repeated, giving longer and longer sorted lists, until a single sorted list is left.

Explanation

A list of one item is already sorted, which is why the splitting stops there. All the sorting happens during the merges, where the front items of two sorted lists are compared. Good answers mention both phases (split, then merge) and say how a merge keeps the items in order.

Mark scheme
  1. 1 mark

    the list is divided / split in half (into two sub-lists)

    max 4. One idea, one mark. Do not credit descriptions of a bubble sort or an insertion sort.

  2. 1 mark

    the splitting is repeated until every sub-list contains only one item

  3. 1 mark

    pairs of (adjacent) sub-lists are merged back together

  4. 1 mark

    when two sub-lists are merged, their first items are compared and the smaller one is put into the new list first (repeatedly), so each merged list is in order

  5. 1 mark

    merging is repeated until there is only one (sorted) list

Question 4

4 marks

This program uses an insertion sort.

array nums = [6, 3, 8, 2]
for i = 1 to 3
    current = nums[i]
    position = i
    while position > 0 AND nums[position - 1] > current
        nums[position] = nums[position - 1]
        position = position - 1
    endwhile
    nums[position] = current
next i

The trace table shows the values at the end of each pass of the for loop (position is shown as it is when the while loop has finished). The first row shows the array before the loop starts. The array values in the last row have been left blank.

Give the values of A, B and C, and the contents of nums at the end of the program.

Trace table with seven columns: i, current, position, nums[0], nums[1], nums[2] and nums[3]. Columns nums[0] to nums[3] are grouped under the heading nums. Row 1: nums[0] = 6, nums[1] = 3, nums[2] = 8, nums[3] = 2; i, current and position blank. Row 2: i = 1, current = 3, position is the letter A, nums[0] = 3, nums[1] = 6, nums[2] = 8, nums[3] = 2. Row 3: i = 2, current is the letter B, position = 2, nums[0] = 3, nums[1] = 6, nums[2] = 8, nums[3] = 2. Row 4: i = 3, current = 2, position is the letter C; nums[0], nums[1], nums[2] and nums[3] blank.

Model answer

i = 1: current = 3. 6 > 3, so 6 moves right and position becomes 0 (A = 0). nums = 3, 6, 8, 2.
i = 2: current = 8 (B = 8). 6 is not greater than 8, so position stays 2.
i = 3: current = 2. 8, 6 and 3 all move right, so position becomes 0 (C = 0).
nums at the end: 2, 3, 6, 8

Explanation

position starts at i and goes down by one each time a bigger item is shifted right, stopping at 0 if current is smaller than everything before it. That is why A and C are both 0: 3 and 2 were each the smallest so far. For 8 the while condition is false straight away, so nothing moves.

Mark scheme
  1. 1 mark

    A = 0

    Correct answers with no working score full marks.

  2. 1 mark

    B = 8

  3. 1 mark

    C = 0

  4. 1 mark

    nums at the end: 2, 3, 6, 8

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.