Matching two sets when you cannot do within-set comparisons
This is the so-called "nuts and bolts" problem, and your pivoting approach can be shown (under uniform choices of pivots) to give a randomized algorithm with expected query complexity $O(n \log n)$, using the analysis of Quicksort as a template.

Fast deterministic algorithms are less obvious. The first true breakthrough paper I know of for this is that of Alon et. al., which shows one simple algorithm with query complexity  $O(n^{1.5} \sqrt{\log n})$ (basically by combining the quicksort approach you describe with a moderately expensive pivot-finding procedure), and another much more involved one with complexity $O(n\,\textrm{polylog}\,n)$ (also based on quicksort, but the identification of the pivot goes through some more hardcore expander machinery).

Subsequently, Komlós et. al. found an asymptotically optimal algorithm with $O(n \log n)$ deterministic query complexity using a different approach based on sorting nets.