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.