7 Mr Rank and Miss File need to sort a pile of examination scripts into increasing order of mark. Mr Rank first goes through the pile of scripts and puts each script into one of two piles, depending on whether the mark is below 50 or not. He then sorts the scripts in the 'below 50 ' pile and Miss File sorts the scripts in the '50 and above' pile. At the end they put the two sorted piles together again.

1. The scripts in the 'below 50' pile have the following marks, starting from the top of the pile. $$\begin{array} { l l l l l l l l } 34 & 42 & 27 & 31 & 12 & 48 & 24 & 37 \end{array}$$ Use bubble sort to sort this list into increasing order. Clearly indicate the list that results at the end of each pass through the algorithm. Give the number of swaps and the number of comparisons that were used in sorting this list.
2. The scripts in the '50 and above' pile have the following marks, starting from the top of the pile. $$\begin{array} { l l l l l l l l } 95 & 74 & 61 & 87 & 71 & 82 & 53 & 57 \end{array}$$ Use shuttle sort to sort this list into increasing order. Clearly indicate the list that results at the end of each pass through the algorithm. List the number of swaps and number of comparisons that were used in sorting this list.
3. Explain why splitting the original list into two piles is a linear order algorithm.
4. Both bubble sort and shuttle sort are quadratic order algorithms. Mr Rank and Miss File use their method to sort a pile of 100 scripts. It takes about 50 seconds to split the pile and about 250 seconds to do each sort. As the sorts are done at the same time, this gives a total time taken of about 300 seconds, or 6 minutes. Approximately how long would Mr Rank and Miss File take to split a pile of 500 scripts into two roughly equal piles and sort the piles? Show all your working.
   [0pt] [4]