Given a set of n nuts of different sizes and n bolts of different sizes. There is a one-one mapping between nuts and bolts. Comparison of a nut to another nut or a bolt to another bolt is not allowed. It means nut can only be compared with bolt and bolt can only be compared with nut to see which one is bigger/smaller.

We will give you a compare function to compare nut with bolt.

 /**

  * public class NBCompare {

  *     public int cmp(String a, String b);

  * }

  * You can use compare.cmp(a, b) to compare nuts "a" and bolts "b",

  * if "a" is bigger than "b", it will return 1, else if they are equal,

  * it will return 0, else if "a" is smaller than "b", it will return -1.

  * When "a" is not a nut or "b" is not a bolt, it will return 2, which is not valid.

 */

 public class Solution {

     /**

      * @param nuts: an array of integers

      * @param bolts: an array of integers

      * @param compare: a instance of Comparator

      * @return: nothing

      */

     public void sortNutsAndBolts(String[] nuts, String[] bolts, NBComparator compare) {

         if (nuts == null || bolts == null) return;

         if (nuts.length != bolts.length) return;

         qsort(nuts, bolts, compare, 0, nuts.length - 1);

     }

     private void qsort(String[] nuts, String[] bolts, NBComparator compare,

                        int l, int u) {

         if (l >= u) return;

         // find the partition index for nuts with bolts[u]

         int part_inx = partition(nuts, bolts[u], compare, l, u);

         // partition bolts with nuts[part_inx]

         partition(bolts, nuts[part_inx], compare, l, u);

         // qsort recursively

         qsort(nuts, bolts, compare, l, part_inx - 1);

         qsort(nuts, bolts, compare, part_inx + 1, u);

     }

     private int partition(String[] str, String pivot, NBComparator compare,

                           int l, int u) {

         int low = l;

         int high = u;

         int i = low;

         while (i <= high) {

             if (compare.cmp(str[i], pivot) == -1 ||

                 compare.cmp(pivot, str[i]) == 1) {

                 swap(str, i, low);

                 i++;

                 low++;

             }

             else if (compare.cmp(str[i], pivot) == 1 ||

                 compare.cmp(pivot, str[i]) == -1) {

                 swap(str, i, high);

                 high--;

             }

             else i++;

         }

         return low;

     }

     private void swap(String[] str, int l, int r) {

         String temp = str[l];

         str[l] = str[r];

         str[r] = temp;

     }

 }