Given a set of n nuts of distinct widths and a set of n bolts such tha
t each nut corresponds to a unique bolt of the same width, how should
we match every nut with its corresponding bolt by comparing nuts with
bolts? (No comparison is allowed between two nuts or two bolts.) The p
roblem can be naturally viewed as a variant of the classic sorting pro
blem as follows. Given two lists of n numbers each such that one list
is a permutation of the other, how should we sort the lists by compari
sons only between numbers in different lists? We give an O(n log n)-ti
me deterministic algorithm for the problem. This is optimal up to a co
nstant factor and answers an open question posed by Alon et al. [Proce
edings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms, 19
94, pp. 690-696]. Moreover, when copies of nuts and bolts are allowed,
our algorithm runs in optimal O(log n) time on n processors in Valian
t's parallel comparison tree model. Our algorithm is based on the AKS
sorting algorithm with substantial modifications.