Lintcode 143. Sort Colors II

Description:

Given an array of n objects with k different colors (numbered from 1 to k), sort them so that objects of the same color are adjacent, with the colors in the order 1, 2, ... k. Example : Given colors=[3, 2, 2, 1, 4], k=4, your code should sort colors in-place to [1, 2, 2, 3, 4].

Code:

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
        int low = 1, high = k, left = 0, right = colors.length-1;
        while(low < high){
            int i = left;
            while(i <= right){
                if(colors[i] == low){
                    swap(colors, i, left);
                    left++;
                    i++;
                }
                else if(colors[i] == high){
                    swap(colors, i, right);
                    right--;
                }
                else{
                    i++;
                }
            }
            low++;
            high--;
        }
    }
    private void swap(int[] colors, int i, int j){
        int temp = colors[i];
        colors[i] = colors[j];
        colors[j] = temp;
    }
}