You are given a mixed pile of n nuts and n bolts. Each nut exactly fits one bolt and viceversa. You can see which one is bigger, smaller or equal by fitting a nut and bolt together, but you can't compare two nuts or two bolts directly. How will you design an algorithm to find the matching pairs of nuts and bolts.
We can find the matching pairs of nuts and bolts by modifying randomized quicksort.
Running time of this algorithm is \( O(n^{2}) \). Let the nuts be denoted by \( [a_1, a_2,...,a_n] \) and bolts be \( [b_1, b_2,...,b_n] \).
