1. [15pts] Suppose you are given N numbers to sort. The N numbers are not known to be in a bounded range. You do, however, know that many of the N

numbers are duplicates. Furthermore, the number of distinct values is "small". "Small" is defined by the property that

M² « N

where M is the number of distinct values.

Give an algorithm that has expected time O(N) to sort the items under the given constraints. Your algorithm must use O(N+ M) space.

Hint: What techniques do you know that make good use of expected-time behavior?