The asymptotic lower bound for sorting n elements is n*log(n)

[flufypancakes]

the asymptotic lower bound for sorting n elements is n*log(n). what about sorting a set of n elements when you know that they only take on k distinct values? does n*log(k) sound right?

 

[hokie1]

Suppose that we could map each of the k values to the integers 1 to k. Also, suppose that we have k values in an array all set to 0. Then a sort would only look once at each number in a list. For each number the value is mapped to an index and the associated array element is incremented. Then the sort is completed by reporting as many values of each type as there are counts in each array element.

cost of inspecting each value n
+ cost of mapping each value from 1 to k ??
+ cost of outputting the sorted list k