2 Shaun measured the mass, in kg, of each of 9 filled bags. He then used an algorithm to sort the masses into increasing order.

Shaun's list after the first pass through the sorting algorithm is given below.

$$\begin{array} { l l l l l l l l l } 
32 & 41 & 22 & 37 & 53 & 43 & 29 & 15 & 26
\end{array}$$

\begin{enumerate}[label=(\roman*)]
\item Explain how you know that Shaun did not use bubble sort.

In fact, Shaun used shuttle sort, starting at the left-hand end of the list.
\item Write down the two possibilities for the original list.
\item Write down the list after the second pass through the shuttle sort algorithm.
\item How many passes through shuttle sort were needed to sort the entire list?

Shaun's sorted list is given below.

$$\begin{array} { l l l l l l l l l } 
15 & 22 & 26 & 29 & 32 & 37 & 41 & 43 & 53
\end{array}$$

Shaun wants to pack the bags into bins, each of which can hold a maximum of 100 kg .
\item Write the list in decreasing order of mass and then apply the first-fit decreasing method to decide how to pack the bags into bins. Write the weights of the bags in each bin in the order that they are put into the bin.
\item Find a way to pack all the bags using only 3 bins, each of which can hold a maximum of 100 kg .
\end{enumerate}

\hfill \mbox{\textit{OCR D1 2016 Q2 [9]}}