Sort Color II

[Problem Description](http://lintcode.com/en/problem/sort-colors-ii/\

[jiuzhang solution](http://www.jiuzhang.com/solution/sort-colors-ii/\

The 'partition' of rainbow sort is different from that of quicksort

class Solution {
    /**
     * @param colors: A list of integer
     * @param k: An integer
     * @return: nothing
     */
    public void sortColors2(int[] colors, int k) {
        // write your code here
        if (colors == null || colors.length == 0) {
            return;
        }
        rainbowSort(colors, 0, colors.length - 1, 1, k);
    }

    public void rainbowSort(int[] colors, int left, int right, int colorFrom, int colorTo){
        if(colorFrom == colorTo){
            return;
        }

        if(left >= right){
            return;
        }

        int colorMid = (colorTo - colorFrom) / 2 + colorFrom;
        int l = left, r = right;
        while(l <= r){
            while(l <= r && colors[l] <= colorMid){ // attention1
                l++;
            }

            while(l <= r && colors[r] > colorMid){ // attention2
                r--;
            }

            if(l <= r){
                colors[l] ^= colors[r];
                colors[r] ^= colors[l];
                colors[l] ^= colors[r];
                l++;
                r--;
            }
        }

        // attention3
        rainbowSort(colors, left, r, colorFrom, colorMid);
        rainbowSort(colors, l, right, colorMid + 1, colorTo);
    }
}