The problem can be stated as the following:
Given a sequence of numbers $a_1, \ldots, a_n$ and $b_1, \ldots, b_n$ such that $\{b_i\}_{i=1}^{n}$ is a permutation of $\{a_i\}_{i=1}^{n}$, find an efficient algorithm which, using only comparisons between $a_i$ and $b_j$ for some $1 \le i, j \le n$, computes the permutation $\sigma$ satisfying $b_{\sigma(i)} = a_i$ for all $1 \le i \le n$.
It's easy to see that the efficiency is $\Omega(n \log{n})$ since the sorting problem can be reduced to this problem.
The original problem I saw allowed the algorithm to be randomized. By modifying quicksort algorithm a little bit we can find the optimal algorithm. (choose a pivot $a_i$, divide all $b_j$ by checking if $b_j$ is bigger/lesser/equal than $a_i$. again choose $b_{\sigma(i)}$ and do the same thing for $a_i$s, separate all lesser/bigger numbers and do the same thing recursively)
My question is that, if we restrict the algorithm to be only deterministic, can we still find the optimal algorithm for the problem?
Sorry for my short and flawed english :D