The election office sorts candidate names alphabetically before ballot papers are checked. Fig. 1 shows a merge-sort operation on two sorted lists of names....
Question 1 Report
The election office sorts candidate names alphabetically before ballot papers are checked. Fig. 1 shows a merge-sort operation on two sorted lists of names. The comparison uses the first letter where all names have different initial letters.
(a) State the first name copied to the output array. [1]
(b) Give the next two names copied. [2]
(c) Give the complete alphabetically sorted output list. [3]
(d) State the comparison made after Amin has been copied. [1]
(e) Explain why the merge operation does not need to compare Amin with every name in List B. [2]
(f) Give one reason a computer may sort names before printing ballot papers. [1]
Answer Details
When merging alphabetically sorted lists, compare only the first unmerged name in each list. Here, the initial letters are all different, so alphabetical order is determined by those letters.
- (a) Amin begins with A and Bello with B, so copy Amin first. [1]
- (b) Next compare Kaur with Bello, so copy Bello; then compare Kaur with Reed, so copy Kaur. The next names are Bello, Kaur. [2]
- (c) The complete output is Amin, Bello, Kaur, Reed, Stone, Young. [3]
- (d) After Amin is copied, the comparison is Kaur with Bello. [1]
- (e) Each list is already sorted. Therefore only the first unmerged name in each list can be the next output name; Amin cannot need comparison with every name in List B. [2]
- (f) Sorting allows names to be printed in a consistent order, or allows staff to find a name more easily. [1]
Download The App On Google Playstore
Everything you need to excel in your exams
