Problem
Suppose that you are given n red and n blue water jugs, all of different shapes and sizes. All red jugs hold different amounts of water, as do all the blue ones. Moreover, for every red jug there is a blue jug that holds exactly the same amount of water.
Your job is to find a matching between red jugs and blue jugs that hold the same amount of water. To do this, you are only allowed to use the following operation: pick a red jug and a blue jug, fill the red jug, and pour it into the blue jug. This will tell you whether the volume of the red jug is less than, equal to, or greater than the volume of the blue jug. In other words, you can compare any red jug and any blue jug. But you cannot compare two red jugs or two blue jugs.
Give a randomized algorithm that uses O(nlogn) comparisons in expectation. Prove that your algorithm is correct and that it uses O(n log n) comparisons in expectation.