QUESTION: Counting each arithmetic calculation or comparison, extraction or exchange of a card as one operation, what is the worst-case order of growth of an algorithm that sorts numbered cards in the following way?

- Find the largest valued card in the deck by shuffling through one card at a time extracting a card if it is the largest one seen so far, and swapping the previously largest card back into the deck. When the largest has been found, place this card face down in a new pile and repeat the previous process until no cars in the original pile are left. Explain your answer.

- This time we assume that the largest number on any of the n cards is n2. We sort the cards by placing a set of n2 plates numbered from 1 to n2 on a table. Then one by one, place each card on top of the numbered plate equal to it on the desk. The sorted list can be extracted by looking through the piles on all n2 plates in order.

- This method can be improved to work in linear time. Explain how. Hint: This is not easy. Use division, to try turn each number into a pair of numbers, each with a value between 1 and n.