Matching two sets when you cannot do within-set comparisons

Suppose you have two lists, A and B, each with length n. The elements of A cannot be compared with other elements of A--there is no order relation among them--and likewise for B. However, elements of A can be compared with elements of B. So for instance, suppose we have a function compareTo(a,b) where a is an element of A and b is an element of B. If a is less than b it returns -1, if they're equivalent it returns 0, and if a is greater it returns 1.

Further suppose that a perfect matching exists between the elements of A and B, in the sense that for every element of A there is precisely one element of B such that compareTo(a,b) evaluates to 0. And vice versa (for each b there is precisely one a such that they're equivalent).

How do we write an efficient algorithm to find the perfect matching?

My attempts: Well, there's the naive algorithm which takes an element of A and finds its corresponding element of B, repeating until all matchings have been found. This runs in O(n^2) so we want to beat this.

It sounds kind of like Gale-Shapley but an input to that algorithm is a preference list. In this setting we have ties, where preference lists don't. And even generating something like a preference list would take n^2 time. Since it is fundamental to Gale-Shapley that members of one set propose to their highest preferences of the other, this doesn't seem applicable to the given problem.

We could try to use an element of A to partition the set B and try to divide-and-conquer. But you would only have divided B and wouldn't know which elements of A to give to the recursive call. You could then try to use B to partition A. To describe this more, let's give a specific example. Suppose A = [a1,a2,a3,a4] and B = [b4,b1,b3,b2] and suppose that ai . We could arbitrarily select a1 and then use it to partition B into the elements that come out greater in the comparison, [b4,b3,b2] and the eleme

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.

StackExchange Computer Science Q#120618, answer score: 4