Sort complexity expressed via distinct number of elements I am reading Probabilistic counting algorithms for database applications. In the introduction an algorithm for finding an intersection is specified:

Sort A, search each element of B in A and retain it if it appears in A.

It is claimed that if a, b are number of elements in A and B, and $\alpha, \beta$ are the number of distinct elements in A, B then the complexity of this algorithm is $O(a\log\alpha + b\log\alpha)$. My question is, why the sorting of A is only dependent on the number of distinct elements? Is there some kind of algorithm I am not aware of? If so, why the same algorithm could not be used for the second strategy? The second strategy is:

Sort A and B, use merge-like operation to discard duplicates.

For this algorithm the complexity is $O(a\log a + b\log b + a + b)$ which makes sense to me.
You can use a balanced binary search tree to sort $A$ in time $O(a\log\alpha)$ by going over the elements of $A$, for each element searching whether it already appears in the tree, inserting it if it isn't already there. You can then perform the second stage in $O(\log \alpha)$ per element of $B$, for a total of $O(b\log\alpha)$.

If you are allowed to use hashing on the elements of $A$ and $B$, then you can use a dynamic hash table to compute the intersection in expected $O(a+b)$ time by using a similar strategy.