[***EDIT: sorry; I saw this nice problem in a book, but it seems a nice deterministic algorithm in $O(n (\log n)^4)$ time was found later, so this answer is inapplicable; reference:***

*Matching nuts and bolts* by Noga Alon, Manuel Blum, Amos Fiat, Sampath Kannan, Moni Naor, Rafail Ostrovsky;

citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.103
]




The "nuts and bolts" problem, which I saw just a few days ago in the Algorithm Design Manual [precise reference to follow when I get time to edit]:

You are given $n$ pairs of nuts and bolts, all very slightly different sizes (so, each nut fits exactly one bolt); but unfortunately they have all been disassembled, and you have to fit them together.

You cannot see the difference in size by eye, so the only way to see if a nut fits a bolt is to try it. If a nut is too large/small for a bolt, you will discover this; but note that *you can't compare two nuts, or two bolts, with each other directly*.

Abstractly: we have 2 real unknown sequences $(x_1, x_2, \ldots, x_n)$ and $(y_1, y_2, \ldots, y_n)$.

The $x_i$ are all distinct, and $(y_j)$ is an unknown rearrangement of $(x_i)$. We want to match them up, but the ONLY measurement we can make is to pick $i,j$ and compare $x_i$ with $y_j$.

The obvious algorithm of trying all of them one-by-one takes $O(n^2)$ time.

However, a variant of *randomised* quicksort takes $O(n \log n)$ time on average. The randomness just comes from picking each nut/bolt at random.

Details: pick a *nut*, use that as the pivot element for the *bolts*; then use the matching *bolt* as the pivot element for the *nuts*, etc. - like quicksort, but going back-and-forth between $x$ and $y$ elements.