Minimal complexity for pairing two comparable sets with comparability restrictions
This is the famous "nuts and bolts" problem.  Yes, there is a randomized algorithm with expected running time $O(n \lg n)$, using a QuickSort-like algorithm.

The problem is famous because there is a simple randomized algorithm that achieves $O(n \lg n)$ expected running time.  However, it's very challenging to find a deterministic algorithm with a $O(n \lg n)$ time running bound.  Therefore, it makes a nice illustration of the utility of randomness.

The problem is described in several algorithms textbooks, including CLRS and Skienna's textbook.