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

 

[quicknote]

Yes, n*log(k) does sound right for sorting a set of n elements when you know they only take on k distinct values. This is because the lower bound for sorting is dependent on the number of comparisons needed to sort the elements. In the case of a set with only k distinct values, the number of comparisons needed will be reduced as there are fewer unique values to sort. Therefore, the lower bound will be n*log(k) instead of n*log(n). This is known as the "distinctness constraint" and is a common factor in lower bounds for sorting algorithms.