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.