# Lower bound Soritng with identical elements

Suppose given an array $$A[1..n]$$ that contains $$k$$ distinct element, why the lower bound for sorting of this instance is $$\Omega(n\log k)$$?

I think according the decision tree the lower bound is $$log \frac{n!}{(n-k)!}.$$ But I can't achive $$\Omega(n\log k)$$.

Suppose that the number of array entries with each distinct element are $$j_1, j_2, \ldots, j_k$$. Note that $$\sum_i j_i = n$$.

Then the number of possible permutations of this array is:

$$\frac{n!}{j_1! j_2! \cdots j_k!}$$

We would like to find what distribution of keys will give us the largest number of permutations.

Glossing over quite a lot of rigour, the number of permutations is maximised in this case:

$$j_1 = \frac{n}{k}, \ldots, j_k = \frac{n}{k}$$

The number of permutations of this array is:

$$\frac{n!}{\left(\frac{n}{k}\right)!^k}$$

And so the minimum number of comparisons required to build a decision tree is:

$$\begin{eqnarray*}\log \frac{n!}{\left(\frac{n}{k}\right)!^k} & \approx & n \log n - k \frac{n}{k} \log \frac{n}{k} \\ & = & n \log k\end{eqnarray*}$$

By the way, the more general result is that the minimum number of comparisons required to sort an array of $$n$$ elements is $$nH$$ where $$H$$ is the zero-order entropy of the key distribution.