The teacher runs an after$-$school computing club and stores the names of children who belong to this club in a list, which at present is unsorted.

Another school close by would like to offer a computer club, but does not have suitable facilities. However, the two schools have reached an agreement allowing children from the second school to attend the computer club run by the first.

The second school has supplied a list, again unsorted, of the names of children from that school who want to belong to the club.

The teacher who runs the club now wants a program that will take the two lists and combine them to eventually produce a single sorted list containing the names of all the children, from both schools, who belong to the club.

She is considering two possible strategies for producing this list.

Strategy $1.$ Append the second school$$s unsorted list to the end of the first school$$s unsorted list, then sort the combined list.

Strategy $2.$ Sort the two lists separately, then combine the sorted lists in a way that results in a single sorted list.

The teacher is interested in exploring how many comparisons between names each sorting strategy uses and which of the two requires the fewer comparisons. She has begun writing a program to investigate these questions and has enlisted you to help her complete it and use it to run some experiments.

For simplicity, we will only use the children$$s first names and assume no two names are the same.

Open the project TM$111\_02\_$Q$4.$sb$2.$ It contains three lists:

school$\_1$ and school$\_2,$ which contain the two unsorted lists from the first and second schools, respectively

merged, which is empty at present; this will hold the final sorted list.

There are also four variables, as follows $($the meaning of $$swapping pass$$ will be described when we come to it$)$:

pass, used to keep track of swapping passes

position, used to keep track of the current position in a swapping pass

temp, used when swapping two adjacent elements

comparison$\_$count, used to count how many pairs of adjacent elements are compared, during sorting and the subsequent merge operation.

In addition there are two components, the custom blocks swapping$\_$pass$\_1$ and swapping$\_$pass$\_2,$ and a when$[1]$key$\_$pressed script. The purpose of these will now be explained.

Note that there is no need for you to modify either of the custom blocks and you should not attempt to do so$.$

a$.$The swapping$\_$pass$\_1$ component and the when$[1]$key$\_$pressed script together form an implementation of bubble sort $2,$ as discussed in Subsection $6\mathrm{.}4\mathrm{.}2$ of Block $2$ Part $6.$ The list they will sort is school$\_1.$

In a bubble sort we perform a series of swapping passes, where each swapping pass consists of working our way through the list to be sorted, comparing pairs of adjacent items, and swapping any pair that is out of order.

Each swapping pass causes an item to $$bubble up$$ and stop at its correct position in the sorted list and so after each swapping pass the unsorted portion of the list becomes one item shorter. Since a swapping pass only needs to consider the unsorted portion, each pass can be one comparison shorter than the previous one.

This is illustrated in Figures $6\mathrm{.}34$ to $6\mathrm{.}37$ of Subsection $6\mathrm{.}4\mathrm{.}2,$ where we observe that bubble sort $2$ will require approximately $($n $1)2/2$ comparisons, where n is the number of items.

It is not too hard to show $($but we will just assume this result$)$ that the exact number is n $\backslash$times $($n $1)/2.$

Make sure the watcher for comparison$\_$count is visible on the stage, then press the $1$ key to execute the when$[1]$key$\_$pressed script.

You should now see that the school$\_1$ list is sorted, and $66$ comparisons were needed. This is the expected number: the length of the list is $12$ and $12\backslash$times $11/2=66.$

Now create a when$[2]$key$\_$pressed that will result in the school$\_2$ list being sorted. You can do this by copying the when$[1]$key$\_$pressed script and carefully making the necessary changes.

i$.$Take a screenshot of your when$[2]$key$\_$pressed script and paste it into your TMA document.

ii$.$Make sure the watcher for comparison$\_$count is visible on the stage, then run your when$[2]$key$\_$pressed script and note how many comparisons were required. Explain what number you were expecting and why, and state whether the result of running the script agrees with your calculation.

Note that you can repopulate the lists for the first and second schools, whenever required using the provided files school$\_1.$txt and school$\_2.$txt and following the procedure described on page $69$ of Block $2,$ Book B$,$ Part $4.$

$(5$ marks$)$

b$.$Next you will write a script to merge the two sorted lists. The idea behind the merging algorithm is that we repeatedly compare the item at the front of the first list with the item at the front of the second list: whichever is the smaller is added to the merged list, then removed from its original list. At some point, one list will become empty and we can then simply append the contents of the other list to