Minimal complexity for pairing two comparable sets with comparability restrictions A project at university (whose deadline has passed by now) presented the following problem:


  Consider two finite sequences of (not necessarily distinct) real
  numbers $a_1,\ldots,a_n$ and $b_1,\ldots,b_n$ such that the $b_k$'s
  are a permutation of the $a_k$'s. The aim is to create an algorithm
  which returns a permutation which maps the sequence $(a_k)$ onto
  $(b_k)$. In order to find such permutation it is necessary to compare
  some numbers during the algorithm. The restriction is that one cannot
  compare any $a_x$ with an $a_y$ or a $b_x$ with a $b_y$: all that is
  allowed is to compare a number of the first sequence with one of the
  second sequence.


I am wondering what would be the minimal (worst-case) complexity of the number of comparisons. It's not hard to get $O(n^2)$: for every $a_x$, search brute-force for a corresponding $b_y$, which costs $O(n)$ comparisons giving a total of $O(n^2)$.
A bit smarter would be to adapt the familiar QuickSort algorithm, in the recursions step taking as a pivot a couple $(a_x,b_y=a_x)$ (which can be found in $O(n)$ comparisons) and partitioning both sequences using this 'pivot'. This gives $\Theta(n\log n)$ comparisons in average, but still $\Theta(n^2)$ worst-case (as usual with QuickSort).

It's not hard to see that $\Omega(n\log n)$ is a minimum: represent a given algorithm as a binary decision tree with a comparison at each node. Since the total number of leaves can reach $\Theta(n!)$ (the number of permutations in case all the $a_k$ are different) the height of the tree is at least $\Omega(\log_2(n!))=\Omega(n\log n)$.

It seems likely that a $O(n\log n)$ algorithm exist, but I have not been able to find one. I have tried adapting MergeSort, but a problem during the merging arises giving a worst-case of $\Theta(n^2)$ nonetheless.

Is this a known problem? Does a $O(n\log n)$ algorithm exist? Do you have suggestions for other known sorting algorithms which might be adapted without increasing their complexity?
This is the famous "nuts and bolts" problem.  Yes, there is a randomized algorithm with expected running time $O(n \lg n)$, using a QuickSort-like algorithm.

The problem is famous because there is a simple randomized algorithm that achieves $O(n \lg n)$ expected running time.  However, it's very challenging to find a deterministic algorithm with a $O(n \lg n)$ time running bound.  Therefore, it makes a nice illustration of the utility of randomness.

The problem is described in several algorithms textbooks, including CLRS and Skienna's textbook.