Matching two sets when you cannot do within-set comparisons

Question

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 < bj if i < j, and likewise for = and >. 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 elements that come out smaller []. Since along the we way we found that a1 matched b1 we make that assignment and eliminate them from the rest of the algorithm. Now that we know a1 was quivalent to b1 we can use b1 to partition A into [] and [a2,a3,a4]. We recursively call the algorithm on the smaller sets [], [] which satisfies the conditions: they have the same length and have perfect matching. And recursively call the algorithm on the larger sets [a2,a3,a4], [b4,b3,b2] which also have the same length and have a perfect matching.

I think this algorithm is correct, but in the worst case it doesn't beat the worst-case runtime of the naive algorithm. So I don't think I'm on the right track here.

Answer 1

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.