Matching cap and pens problem.

Given N pens and n caps . Sort them. you cant compare pens with other pens and caps with other caps. - Originally known as Matching Nuts and Bolts problem.


Approach:
Pens = {P3, P2, P1, P5, P4}
Caps = {C4, C1, C5, C2, C3}


We are going to use a modified version of quick sort to solve this.


Choose one of the pens as pivot say P3, find the cap for P3.


Now compare every pen with C3 (cap for P3) and divide the pen around pivot P3, 
Similarly compare every cap with P3 and divide the caps around the pivot C3, 
We now have the arrays as:
Pens = {P2, P1} +  P3 + {P5, P4} - P3 is now at its correct position if Pens array would have been sorted.
Caps = {C1, C2} +  C3 + {C4, C5} - C3 is now at its correct position if Caps array would have been sorted.


Now run the above steps recursively of the left and right subproblems.


Time complexity: T(n) = T(k) + T(n-k) + O(n)
= O(n^2)
Average case: O(nlogn) - we can use the randomized pivots to achieve O(nlogn) as expected time (averaged over all choices of pivots).


Space complexity: Quick sort is an inplace algorithm so space complexity - O(1)