Joining lists with some common elements in average case What are some ways of commutatively combining a pair of lists to produce a list comprised of elements from the pair of inputs, with no duplicates, with time complexity better than $O(n \log(n))$? Suppose we have the following inputs

$a = [5, 1, 6, 8]$

$b = [8, 4, 5, 2, 10]$

We would like to commutatively combine $a$ and $b$ to produce a list with no duplicate elements (i.e. if F denotes a function that satisfies the aforementioned criteria, then $\forall x, y \quad F(x, y) = F(y, x)$). One possible valid output is $c = [1, 2, 4, 5, 6, 8, 10]$ - since the output doesn't have to be sorted, any permutation of $c$ is just as valid (although consistency would be nice). The most obvious naïve algorithm concatenates the two lists, then removes duplicates, then sorts the result in $O(n \log(n))$ time.

Is there a commonly used name for this kind of problem, and where can I find literature about it?
Yes and no.

Set interaction is one of the problems specifically studied in Ben-Or's seminal paper on lower bounds for algebraic decision and computation trees.  The problem is formally defined as follows: Given two sets of n numbers, is their intersection empty? Equivelently, does their union have exactly 2n elements?  Ben-or proves a lower bound of Ω(n log n) for this problem.  If the sets have diffent sizes n>m, the lower bound becomes Ω(n log m), but this only beats the naive O(n log n) bound if m is subpolynomial in n.

On the other hand, if your list elements are integers, you can solve the problem in o(n log n) time using fast integer-RAM sorting algorithms.  For reasonable word sizes, I believe the fastest integer sorting algorithm runs in $O(n \sqrt{\log \log n})$ expected time [Han and Thorup, FOCS 2002].