Question 1
2 marksA 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 mark
4 stages of splitting
16, 8, 4, 2, 1
-
1 mark
4 stages of merging
1, 2, 4, 8, 16