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?
Fig: 1