Chhetri AcademyGCSE & A level Paper Builder

Merge sort

OCR GCSE Computer Science (J277) · Algorithms and programming (Paper 2) › Algorithms › Searching and sorting algorithms

Practise Merge sort. 12 exam-style questions plus unlimited generated ones on this subtopic, at up to four difficulty levels, with full mark schemes and a progress tracker. Free, no account needed.

Build a paper on this topic

▶ Watch videos on Merge sort (Craig 'n' Dave OCR on YouTube) · Practise all of Searching and sorting algorithms

Quick recall

Cover the answers and test yourself. The app has these as flashcards that come back just before you'd forget them.

During a merge sort, the sorted lists [2, 8] and [5, 9] are merged into one list. State the merged list.
2, 5, 8, 9

Sample questions

Written for this site in the style of OCR exam questions. They are not taken from real past papers.

Question 1Easy4 marks
(a) Describe the first stage of a merge sort.[2]
(b) Which statement about merge sort is true?
Tick (✓) one box.[1]
  • It only works on lists that are already sorted
  • It is usually more efficient than a bubble sort for large lists
  • It compares each item with the item next to it and swaps them
  • It can only sort numbers, not words
(c) Give one disadvantage of a merge sort compared with a bubble sort.[1]
Show the answer and mark scheme
(a)
  • the list is repeatedly divided / split in half
  • until each sub-list contains only one item
(b) Answer: It is usually more efficient than a bubble sort for large lists
(c)
  • uses more memory (to store the sub-lists)
  • more complex to code / understand
  • carries out all the splitting and merging even if the list is already sorted
  • can be slower for very small lists
Question 2Medium5 marks
A merge sort is used to sort a list of toys into alphabetical order. The list has already been split into single items:
[kite] [drum] [yoyo] [ball] [top] [doll] [sled] [bike]
(a) Show the lists after each stage of merging.[3]
(b) Give one advantage and one disadvantage of merge sort compared with bubble sort.[2]
Show the answer and mark scheme
(a) Answer: [drum, kite] [ball, yoyo] [doll, top] [bike, sled]
[ball, drum, kite, yoyo] [bike, doll, sled, top]
[ball, bike, doll, drum, kite, sled, top, yoyo]
  • [drum, kite] [ball, yoyo] [doll, top] [bike, sled]
  • [ball, drum, kite, yoyo] [bike, doll, sled, top]
  • [ball, bike, doll, drum, kite, sled, top, yoyo]
(b)
  • advantage: more efficient / quicker for large lists
  • disadvantage: uses more memory / is more complex to program
Question 3Hard7 marks
The function below merges two sorted arrays, a and b, into one sorted array. Lines 21 to 25 are missing.
01 function merge(a, b)
02    array result[a.length + b.length]
03    i = 0
04    j = 0
05    k = 0
06    while i < a.length AND j < b.length
07       if a[i] <= b[j] then
08          result[k] = a[i]
09          i = i + 1
10       else
11          result[k] = b[j]
12          j = j + 1
13       endif
14       k = k + 1
15    endwhile
16    while i < a.length
17       result[k] = a[i]
18       i = i + 1
19       k = k + 1
20    endwhile
21    ............
22    ............
23    ............
24    ............
25    ............
26    return result
27 endfunction
(a) The function is called with a = [4, 10, 13] and b = [6, 7].
State the values of i, j and k when the loop on lines 06 to 15 ends.[2]
(b) Write the missing code for lines 21 to 25.[3]
(c) Explain whether the function would still produce a correctly sorted array if line 07 used < instead of <=.[2]
Show the answer and mark scheme
(a) Answer: i = 1, j = 2, k = 3
  • i = 1 and j = 2
  • k = 3
(b) Answer: 
while j < b.length
   result[k] = b[j]
   j = j + 1
   k = k + 1
endwhile
  • a loop that runs while j < b.length
  • copies b[j] into result[k]
  • increases both j and k by 1 inside the loop
(c)
  • yes, the result would still be sorted
  • when a[i] and b[j] are equal it does not matter which is placed first, because the other one is placed straight after it

Related subtopics

Stuck? Get 1-to-1 help. Chhetri Academy tutors GCSE and A level Maths and Science online, with a free 30-minute trial lesson.

Book a free trial