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?