Answer Happy

Question 64 In lectures we saw how use the Merge sort algorithm to sort a sequence of length n=2" into ascending order. In fact the algorithm can be applied to sequences of any length n E N. At each iteration the current sorted sub-sequences are merged in pairs as for the 2" case but if there are an odd number of sub-sequences then the 'left over? one just joins, unchanged, the newly formed sub-sequences 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 Oth iteration (P), (R),(0),(V),(I), (S),(I),(0),(N),(A), (L); after 1st iteration (P,R),(0,1),(1,5),(1,0),(A,N), (L); after 2nd iteration (0,P,R,V),(1,1,0,1),(A,L,N); after 3rd iteration (1,1,0,0,P,R,S,V),(A,L,N); after 4th iteration (A,1,1,1,1,0,0,P, R, S,V). (a) Apply the Merge sort algorithm to sort the letters of the word STEREOPHOTOGRAPHIC into alphabetical order, showing the results of each iteration as in the example above. (b) How many comparison operations are used to merge sort STEREOPHOTOGRAPHIC? As in Worksheet Q5, 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 first iteration, 8 in the 2nd, 7 in the 3rd and 5 in the last. (c) How many comparison operations would be used if STEREOPHOTOGRAPHIC were sorted using the Selection sort algorithm?