# Deterministic algorithm for matching variables by only using restricted comparison

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

-
What does it mean to restrict the algorithm to be only deterministic? Presumably the "randomized" algorithm uses a deterministic pseudo-random number generator? How would you distinguish a "deterministic" algorithm from such a "randomized" algorithm? –  joriki Jul 24 '11 at 9:57
Just to clarify, we're not allowed to (directly) compare $a_i$ with $a_j$, or $b_i$ with $b_j$, right? (If we can do that, it should be easy to reduce the problem back to sorting.) –  Ilmari Karonen Jul 24 '11 at 10:12
@joriki Sorry for confusion. What I mean by randomized algorithm is that it uses pure "ideal" random number generator and its efficiency for a input is measured by the expected value of the time taken by the algorithm. The "randomized" algorithm's efficiency is the maximum of efficiency for all inputs can be made. –  Jineon Baek Jul 24 '11 at 10:33
@joriki "deterministic" algorithm never uses a pure "ideal" random number generator. So it can use PRNG or whatsoever. However its efficiency is measured by the maximum of efficiency for all inputs can be made(efficiency for a input is measured by just time taken for that input). –  Jineon Baek Jul 24 '11 at 10:35
@Ilmari Karonen Sorry for confusion again. YES :-) –  Jineon Baek Jul 24 '11 at 10:36