package lintcode.sorting;

/**
 * Created by cdai on 1/8/17.
 */
public class Solution {

    // 143-Sort colors II
    // Each round put color-1 to front and color-k to back in same manner
    public void sortColors2(int[] colors, int k) {
        int l = 0, r = colors.length - 1;
        for (int c1 = 1, ck = k; c1 < ck && l < r; c1++, ck--) {
            for (int m = l; m <= r; m++) {
                if (colors[m] == c1) swap(colors, l++, m);
                else if (colors[m] == ck) swap(colors, r--, m--);
            }
        }
    }

    private void swap(int[] nums, int a, int b) {
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }

}

@@ -674,10 +674,420 @@
 %0A    %7D%0A%0A
+    // 6-Merge Two Sorted Array%0A    public int%5B%5D mergeSortedArray(int%5B%5D A, int%5B%5D B) %7B%0A        int m = A.length, n = B.length;%0A        int%5B%5D C = new int%5Bm + n%5D;%0A        int i = 0, j = 0, k = 0;%0A        while (i %3C m && j %3C n)%0A            C%5Bk++%5D = (A%5Bi%5D %3C B%5Bj%5D) ? A%5Bi++%5D : B%5Bj++%5D;%0A%0A        if (i %3C m) System.arraycopy(A, i, C, k, m - i);%0A        else System.arraycopy(B, j, C, k, n - j);%0A        return C;%0A    %7D%0A%0A
 %7D%0A

merge sorted array