4
$\begingroup$

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

  • 0
    @J.M.: There are other $O(n \log n)$ worst case sorting algorithms, such as mergesort. There's a table of best/worst/average case performance of various sorting algorithms at [Wikipedia](http://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms). But I guess it's all academic now that the original question has been answered.2011-07-24

1 Answers 1

5

This problem is known as “matching nuts and bolts,” posed by Alon, Blum, Fiat, Kannan, Naor, and Ostrovsky [ABF+94]. It was solved by Komlós, Ma, and Szemerédi [KMS98], who gave a deterministic O(n log n)-time algorithm. This is optimal for the reason which you stated in the question.

[ABF+94] Noga Alon, Manuel Blum, Amos Fiat, Sampath Kannan, Moni Naor, and Rafail Ostrovsky. Matching nuts and bolts. In Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA ’94), pp. 690–696, 1994. http://portal.acm.org/citation.cfm?id=314673

[KMS98] János Komlós, Yuan Ma, and Endre Szemerédi. Matching nuts and bolts in O(n log n) time. SIAM Journal on Discrete Mathematics, 11(3):347–372, 1998. http://dx.doi.org/10.1137/S0895480196304982