Suppose that there are n nuts and bolts. A simple modification of Quicksort shows that there are randomized algorithms whose expected number of comparisons (and running time) are O(n log n): pick a random bolt, compare it to all the nuts, find its matching nut and compare it to all the bolts, thus splitting the problem into two problems, one consisting of the nuts and bolts smaller than the matched pair and one consisting of the larger ones. Repeating in this manner yields an algorithm whose expected running time can be analyzed by imitating the known analysis for Quicksort (see, e.g., the book by Coreman, Leiserson and Rivest, Algorithms, MIT Press, 1990.) showing that it is O(n log n).
Is this the best possible? There are n! possibilities for matching the nuts and bolts a priori. Every attempted matching between a nut and a bolt has three possible outcomes (they match, the nut is larger, the nut is small). Therefore the information theoretic lower bound shows that any bounded degree decision tree that solves the problem has depth at least log (n!)= Theta (n log n). This is a lower bound for the expected number of comparisons in any randomized algorithm for the problem as well.
The nuts and bolts matching problem was invented by G. J. E. Rawlins who gives it as an exercise in his book Compared to what? an introduction to the analysis of algorithms, Computer Science Press, 1991, on page 293. He gives the above outlined solution.
What about deterministic algorithms? They seem more difficult to find. In fact, even obtaining an o(n^2) algorithm appears to be a non-trivial task. Here is a paper (Postscript, gzipped Postscipt) by Noga Alon, Manuel Blum, Amos Fiat, Sampath Kannan, Moni Naor and Rafi Ostrovsky (appeared in SODA 94) that describes an almost asymptotically optimal deterministic algorithm. Recently, Janos Komlos, Yuan Ma and Endre Szemeredi found a deterministic O(n log n) algorithm (appeared in SODA 96 ).
Back to the Matching Nuts and Bolts puzzle