2. (30 points) Bob, the builder, has a set N of n nuts and a set B of n bolts, such that each nut in N has a unique matching bolt in B. Unfortunately, the nuts in N all look the same, and the bolts in B all look the same as well. The only kind of comparison that Bob can make is to take a nut-bolt pair (a,b), such that a N and b B, and test it to see if the threads of a are larger, smaller, or a perfect match with the threads of b. Describe an efficient algorithm for Bob to match up all the nuts in N with the corresponding bolts in B. What is the average running time of this algorithm in terms of nut-bolt comparisons that Bob must do? This is a great interview question. It's probably easy to come up with the straightforward, ineff cient solution. The non-trivial solution, on the other hand, requires some thinking. How about we apply the spirit of "partitioning" from quicksort here