The school robotics club records the times, in seconds, taken by six robots to complete a maze. Fig. 1 shows how a merge-sort algorithm divides the array be...
Question 1 Report
The school robotics club records the times, in seconds, taken by six robots to complete a maze. Fig. 1 shows how a merge-sort algorithm divides the array before it combines the values. Each box is a sub-array held in memory.
(a) State the sorting algorithm shown in Fig. 1. [1]
(b) Give the two sorted sub-arrays produced when [14, 7, 19] is fully sorted. [2]
(c) Give the result of merging [7, 14, 19] with [4, 9, 11]. [2]
(d) State one reason merge sort needs extra memory while it is running. [1]
Answer Details
Merge sort repeatedly divides an array into smaller sub-arrays, sorts them, then merges sorted sub-arrays back together.
- (a)The algorithm is merge sort. [1]
- (b)For the section
[14, 7, 19], the split sub-arrays shown are[14]and[7, 19]; once that section is fully merged in order, it is[7, 14, 19]. The supplied mark scheme accepts[7]and[14, 19], or the correctly ordered final section[7, 14, 19]. The wording “two sorted sub-arrays produced when [14, 7, 19] is fully sorted” is therefore somewhat unclear, because[4, 9, 11]belongs to the other original half. [2] - (c)Merging
[7, 14, 19]with[4, 9, 11]gives[4, 7, 9, 11, 14, 19]. At each step, choose the smaller front value from the two sorted lists. [2] - (d)Merge sort needs temporary sub-arrays, or a second array, while merging values. This is why it requires extra memory. [1]
Download The App On Google Playstore
Everything you need to excel in your exams
