Problems in Algorithams?

Question

Assume that we are given a set of n numbers with many repetitions.The number of distinct values is k,where k is much smaller than n.Using comparisons only,develop an algoritham that sorts the elements of the set in O(n log k) time in the worst case.

Answer 1

You don't state whether or not the numbers are integers. If so, radix sort satisfies your criteria; it has performance of O(n log k) where the log is to the base in which the integers are represented.