Why Counting Sort is mathematically incorrect here:
Counting Sort has a time complexity of $O(n + M)$, where $n$ is the number of elements and $M$ is the difference between the maximum and minimum values in the array (the range).
The problem states there are $k$ distinct numbers, but it does not bound their values.
If your array is [1, 1000000000, 1, 1000000000], then $n = 4$ and $k = 2$. However, Counting Sort would require an auxiliary array of size $1,000,000,000$ and take $O(10^9)$ time. This is wildly inefficient and clearly not the intended "optimal" algorithm.
Approach : Worst-Case $O(n \log k)$
To achieve a strict worst-case bound, we use a self-balancing Binary Search Tree ..
Pseudo-code:
Algorithm SortKDistinct(A, n):
Initialize an empty balanced BST (e.g., AVL Tree)
// Step 1: Count frequencies using the BST
For i = 1 to n:
Node = BST.Search(A[i])
If Node exists:
Node.count = Node.count + 1
Else:
BST.Insert(A[i] with count = 1)
// Step 2: Reconstruct the sorted array
Index = 1
For each Node in BST.InOrderTraversal():
While Node.count > 0:
A[Index] = Node.value
Index = Index + 1
Node.count = Node.count - 1
Return A
Time Complexity Analysis:
Step 1: We insert/search $n$ elements into a BST. Because there are only $k$ distinct elements, the BST will never exceed a size of $k$. Therefore, the maximum height of the tree is $O(\log k)$. Processing $n$ elements takes exactly $O(n \log k)$ time.
Step 2: An in-order traversal of a BST with $k$ nodes takes $O(k)$ time. Writing the $n$ elements back to the array takes $O(n)$ time. Total for Step 2 is $O(n)$.
Overall Worst-Case Time Complexity: $O(n \log k) + O(n) = \mathbf{O(n \log k)}$.
Space Complexity: $\mathbf{O(k)}$ to store the BST.
Approach : Expected $O(n + k \log k)$
we often use Hash Maps. We can count the frequencies in $O(n)$ expected time, extract the $k$ distinct keys, sort just those $k$ keys in $O(k \log k)$ time, and rebuild the array.
While practically faster because $O(n + k \log k) \le O(n \log k)$, algorithm purists often prefer the BST method for formal proofs because standard hashing has a worst-case $O(n^2)$ time if many collisions occur (
Deep Analysis: Why $O(n \log k)$ is theoretically optim
if we know the array is a multiset (an array with duplicates) containing $n$ elements but only $k$ distinct values with frequencies $f_1, f_2, ..., f_k$, the number of possible unique permutations is:
$$\frac{n!}{f_1! \cdot f_2! \dots f_k!}$$
Taking the base-2 logarithm of this value (using Stirling's approximation) gives us the minimum number of comparisons required to sort it. Mathematically, this bounds to exactly $\Omega(n \log k)$ in the worst case (where each of the $k$ elements appears $n/k$ times).
Therefore, the $O(n \log k)$ balanced BST algorithm is not just a good idea; it is provably, mathematically optimal for comparison-based sorting of multisets with unknown element bounds.
1. Mathematical Derivation: How $n \log k$ Occurs
The number of comparisons required to sort a sequence is determined by the Entropy of the possible permutations. In a standard sort of $n$ unique elements, there are $n!$ permutations, and $\log_2(n!) \approx n \log n$.
However, in a multiset with $n$ total elements and $k$ distinct elements with frequencies $f_1, f_2, \dots, f_k$, the number of distinct permutations $W$ is given by the multinomial coefficient:
$$W = \frac{n!}{f_1! \cdot f_2! \dots f_k!}$$
To find the minimum comparisons ($C$), we take the base-2 logarithm and use Stirling’s Approximation ($\ln n! \approx n \ln n - n$):
$$\log_2 W = \log_2(n!) - \sum_{i=1}^{k} \log_2(f_i!)$$
$$\log_2 W \approx (n \log_2 n - n) - \sum_{i=1}^{k} (f_i \log_2 f_i - f_i)$$
Since $\sum f_i = n$, the "$-n$" and "$-(-n)$" terms cancel out:
$$\log_2 W \approx n \log_2 n - \sum_{i=1}^{k} f_i \log_2 f_i$$
Now, let $p_i = \frac{f_i}{n}$ be the probability of picking the $i$-th distinct element. Substituting $f_i = n p_i$:
$$\log_2 W \approx n \log_2 n - \sum_{i=1}^{k} (n p_i) \log_2 (n p_i)$$
$$\log_2 W \approx n \log_2 n - \left[ \sum n p_i \log_2 n + \sum n p_i \log_2 p_i \right]$$
$$\log_2 W \approx n \log_2 n - n \log_2 n \underbrace{(\sum p_i)}_{1} - n \sum p_i \log_2 p_i$$
$$\log_2 W \approx n \left( -\sum_{i=1}^{k} p_i \log_2 p_i \right) = n \cdot H$$
Where $H$ is the Shannon Entropy of the frequency distribution.
The Worst Case: Entropy $H$ is maximized when all $k$ elements are equally frequent ($p_i = 1/k$).
In this case, $H = -\sum \frac{1}{k} \log_2 \frac{1}{k} = \log_2 k$.
Finally : The lower bound is $\Omega(n \log k)$.
