Efficent deterministic algorithm to sort n numbers with many duplicates ( distinct integers $O(\log n)$)
How much time does it take to make $\Theta(n)$ queries in a Red-Black Tree with size $O(\log n)$ ?
A detailed solution follows:

Let $T$ be a new empty self-balancing search tree storing pairs of integers, where the order property is w.r.t. the first element of each pair. For each element $A[i]$ of the original array, query $T$ for a node which first element is $A[i]$. If there is no such node, insert a new node $(A[i], 1)$; otherwise, update the node $(A[i], m)$ with $(A[i], m+1)$.
After you are done with all the elements in A, clear $A$ and visit $T$ in-order. For each node $(x, m)$ of $T$, append $m$ copies of $x$ to $A$. Correctness is trivial, and to prove the complexity bound it is sufficient to observe that at any given time the size of $T$ is $O(\log n)$.