Pens and Caps

You have $n$ pens, and $n$ caps for the pens. For every pen, there is exactly one cap that fits. The rest are either loose or tight.

Someone has taken the caps out and jumbled them up. Can you fit the caps on their respective pens, in expected $O(n \log n)$ time?

[Solution]