In lectures we saw how use the Merge sort algorithm to sort a sequence of length n = 2r into ascending order. In fact the algorithm can be applied to sequences of any length n ?N. At each iteration the current sorted subsequences are merged in pairs as for the 2r case but if there are an odd number of subsequences then the left over one just joins, unchanged, the newly formed subsequences at the next iteration. This will mean that the merge algorithm will sometimes need to merge sequences of unequal lengths, but this causes no problems. For example, if Merge sort is used to sort the letters of the word PROVISIONAL into alphabetical order then the subsequences at each stage will be: after 0th iteration (P),(R),(O),(V),(I),(S),(I),(O),(N),(A),(L); after 1st iteration (P,R),(O,V),(I,S),(I,O),(A,N),(L); after 2nd iteration (O,P,R,V),(I,I,O,S),(A,L,N); after 3rd iteration (I,I,O,O,P,R,S,V),(A,L,N); after 4th iteration (A,I,I,L,N,O,O,P,R,S,V).

(a) Apply the Merge sort algorithm to sort the letters of the 10-letter word XENOPHOBIC into alphabetical order and carefully count the number of comparisons used. Remember that when the merge algorithm reaches the stage where one of its input lists is empty, it does not need any more comparisons to complete its task. For example, for PROVISIONAL there are only 5 comparisons during the ?rst iteration, 8 in the 2nd, 7 in the 3rd and 5 in the last. The number of comparisons used to Merge sort XENOPHOBIC is?

(b) What are the maximum and minimum numbers of comparisons that Merge sort would use on a 10-item list, taking into account all possible original orderings of such a list? The minimum number of comparisons used to Merge sort a 10-item list is ? The maximum number of comparisons used to Merge sort a 10-item list is ?

(c) Recall that an upper bound on the number of comparisons used in a Merge sort is the number of transfers (which depends only on the length of the list). Carefully count the number of transfers used in Merge sorting XENOPHOBIC and hence determine: The number of transfers used to Merge sort a 10-item list is ?

(d) For a list of length n=2r we have seen that the number of transfers used by Merge sort is r2r. In this case r=log2 n, so when n is not a power of 2 we can hope to get an approximation to the number of transfers as dnlog2 ne (d...e denotes the ceiling function, and log2 n = logn/log2.) For n=10 the value of the approximation dnlog2 ne is ?

(e) The number of comparison operations used to Selection sort a 10-item list is?