1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

public void merge(int A[], int m, int B[], int n) {
        int i = m - 1; // 指针i：指向A有效元素的最后一位
        int j = n - 1; // 指针j：指向B有效元素的最后一位
        int k = m + n - 1; // 指针k：指向A物理空间的最后一位（合并后元素的存放位置）

        // 同时遍历A、B的有效元素，取较大值放到A的k位置
        while (i >= 0 && j >= 0) {
            if (A[i] > B[j]) {
                A[k--] = A[i--];
            } else {
                A[k--] = B[j--];
            }
        }

        // 若A的有效元素先遍历完，将B剩余元素依次放入A的剩余位置
        if (i < 0) {
            while (j >= 0) {
                A[k--] = B[j--];
            }
        }
    }