[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.

[EDIT: disclaimer! I probably shouldn't have posted this answer, because it's nowhere near my area of expertise; so beware, it may contain nonsense!]

[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.

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 the fact that all nuts/bolts are in a random order, so when you pick one, it is effectively 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.

[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.