Give an optimal algorithm in pseudo-code for sorting a sequence of n numbers which has only k distinct numbers (k is not known a Priori). Give a brief analysis for the time-complexity of your algorithm.

GATE 1991 · Algorithms · Sorting · hard

Answer: Optimal algorithm uses a frequency map + sort of k keys. Time complexity: O(n + k log k), which is O(n log k) in the worst case.

1. Pseudo-code of algorithm: Algorithm SortWithKDistinct(A[1..n]): freq = empty hash map for i = 1 to n do freq[A[i]] = freq[A[i]] + 1 // count frequencies, O(n) keys = list of all keys in freq // k distinct keys Sort(keys) // sort k keys: O(k log k) idx = 1 for each x in keys (sorted) do for j = 1 to freq[x] do A[idx] = x idx = idx + 1 // write back: O(n) return A
2. Time complexity analysis: Since k <= n: k log k <= n log n, but also k log k <= n log k. The dominant term depends on k. If k << n then O(n) dominates; if k = Theta(n) then O(n log n). In general the complexity is O(n + k log k). This is optimal because: reading n elements takes Omega(n), and sorting k distinct values needs Omega(k log k) by comparison lower bound. So the algorithm is optimal.