Merge sorted array

想法很簡單就是開一個 temp array，然後比較兩邊的結果，小的先放入

public void mergeSortedArray(int[] A, int m, int[] B, int n) {
    int[] results = new int[m+n];

    int p1 = 0;
    int p2 = 0;
    int index = 0;
    while (p1 < m && p2 < n) {
        if (A[p1] < B[p2]) {
            results[index++] = A[p1++];
        } else if (A[p1] > B[p2]) {
            results[index++] = B[p2++];
        } else if (A[p1] == B[p2]) {
            results[index++] = A[p1++];
            results[index++] = B[p2++];
        }
    }

    if (p1 < m) {
        while (p1 < m) {
            results[index++] = A[p1++];
        }
    }

    if (p2 < n) {
        while (p2 < n) {
            results[index++] = B[p2++];
        }
    }

    for (int i=0; i<results.length; i++)
        A[i] = results[i];
}

此題有另一個方法是不開 temp array，該怎麼做?

題目有說 A 後面的空位可以塞的下 B，不過不是從前面開始比，

從前面開始比，後面的元素還要移位，所以我們可以從 A B 最後一個元素開始比，

比較大的就放到 A 的最後一個位置

public void mergeSortedArray(int[] A, int m, int[] B, int n) {
    int lastPos = m+n-1;
    int p1 = m-1;
    int p2 = n-1;
    while (p1 >= 0 && p2 >= 0) {
        if (A[p1] > B[p2]) {
            A[lastPos--] = A[p1--];
        } else if (A[p1] < B[p2]) {
            A[lastPos--] = B[p2--];
        } else {
            A[lastPos--] = B[p2--];
            A[lastPos--] = A[p1--];
        }
    }

    if (p1 >= 0) {
        while (p1 >= 0) {
            A[lastPos--] = A[p1--];
        }
    }
    if (p2 >= 0) {
        while (p2 >= 0) {
            A[lastPos--] = B[p2--];
        }
    }
}