Time complexity of set intersection
Your post contains two problems. I will only address the first.

There is a simple $O(n)$ algorithm for computing $A \cap B$, which involves an array of length $n$.

Another algorithm sorts $A \cup B$ to find the intersection in time $O(n\log n)$. In contrast to the previous algorithm, this algorithm can be implemented using only comparisons. There is a matching $\Omega(n\log n)$ lower bound in the algebraic decision tree model; see for example lecture notes of Otfried Cheong.