Lintcode: Nuts & Bolts Problem

quick sort非常好的题。用bolts[start]将nuts partition成两部分，得到中间值pivot，再用nuts[pivot]将bolts分成两部分。再对pivot两边进行recursion

public class Solution {
    public void sortNutsAndBolts(int[] nuts, int[] bolts) {
        if (nuts == null || nuts.length <= 1) {
            return;
        }
        sub(nuts, bolts, 0, bolts.length - 1);
    }
    private void sub(int[] nuts, int[] bolts, int start, int end) {
        if (start >= end) {
            return;
        }
        int pivot = bolts[start];
        //sort nuts using bolt as pivot
        int index = sortNuts(nuts, pivot, start, end);
        //sort bolts using nuts[j-1] as pivot
        pivot = nuts[index];
        sortBolts(bolts, pivot, start, end);
        sub(nuts, bolts, start, index - 1);
        sub(nuts, bolts, index+1, end);
    }
    private int sortNuts(int[] nuts, int pivot, int start, int end) {
        int i = start-1, j = end+1;
        for (int index = start; index < j; index++) {
            if (Compare.cmp(nuts[index], pivot) == -1) {
                int tmp = nuts[++i];
                nuts[i] = nuts[index];
                nuts[index] = tmp;
            } else if (Compare.cmp(nuts[index], pivot) == 1) {
                int tmp = nuts[--j];
                nuts[j] = nuts[index];
                nuts[index] = tmp;
                index--;
            }
        }
        return j-1;
    }
    private int sortBolts(int[] bolts, int pivot, int start, int end) {
        int i = start-1, j = end+1;
        for (int index = start; index < j; index++) {
            if (Compare.cmp(pivot, bolts[index]) == -1) {
                int tmp = bolts[--j];
                bolts[j] = bolts[index];
                bolts[index] = tmp;
                index--;
            } else if (Compare.cmp(pivot, bolts[index]) == 1) {
                int tmp = bolts[++i];
                bolts[i] = bolts[index];
                bolts[index] = tmp;
            }
        }
        return j-1;
    }
};