You have some nuts and some bolts in random order. You cannot compare nuts with nuts and bolts with bolts. It is guaranteed that a nut will fit in one or more bolts. Now you have to sort both nuts and bolts separately in minimum complexity.

You have some nuts and some bolts in random order. You cannot compare nuts with nuts and bolts with bolts. It is guaranteed that a nut will fit in one or more bolts. Now you have to sort both nuts and bolts separately in minimum complexity.


I used quick sort approach and sorted both in n * log (n). (The exact solution I am not posting it, quick sort is a hint).
Take a bolt and use it as pivot to find the smaller, matching and the bigger nuts. Now using this nut as pivot, partially sort the bolts. Now continue with the left and right halves, recursively.