Two sets of items. Each element of set A a unique match in set B. Match each item of set A to item in set B in O(nlogn) time

Question

So, to clarify the question:

Set A and Set B every element in set A has a partner in set B you can not sort either set based upon comparing it to members of the same set, ie, each b element of B is indistinguishable from any other b of set B (likewise for A). when Ai is matched with Bi you can tell if Bi > Ai, Bi < Ai or Bi = Ai. design an algorithm with O(nlogn) running time.

The obvious answer with quadratic time is trivial and not helpful -- although it's the best I've come up with yet. The log(n) makes me think that I should be using recursion or a binary tree of some sort, but I'm not sure how could create a binary tree without being able to compare elements from the same set. Also, I'm not sure how to use a recursive call to any greater effect than just running nested for loops. Any tips would be greatly appreciated.

Answer 1

You haven't stated it very clearly, but your question looks suspiciously like the Matching Nuts and Bolts problem.

The idea there is to pick a random nut a, find the matching bolt b. Partition the bolts using nut a, and partition the nuts using Bolt b, and then recurse, like quicksort does.

(Of course, we are talking about the average case being nlogn, rather than the worst case).