设子数组A[0:k]和A[k+1:N-1]已排好序(0≤K≤N-1)。试设计一个合并这2个子数组为排好序的数组A[0:N-1]的算法。要求算法在最坏情况下所用的计算时间为O(N),只用到O(1)的辅助空间。

可以使用双指针法将两个有序子数组合并为一个有序数组。

具体做法是，设两个指针i和j分别指向两个子数组的起始位置，比较A[i]和A[j]的大小，将较小的元素放入新数组A的末尾，并将对应指针向后移动一位，直到其中一个指针到达末尾。此时，将另一个子数组剩余的元素依次放入新数组A的末尾即可。

代码实现如下：

void merge(int A[], int start, int mid, int end) {
    int i = start, j = mid + 1, k = 0;
    int tmp[end - start + 1];
    while (i <= mid && j <= end) {
        if (A[i] <= A[j]) {
            tmp[k++] = A[i++];
        } else {
            tmp[k++] = A[j++];
        }
    }
    while (i <= mid) {
        tmp[k++] = A[i++];
    }
    while (j <= end) {
        tmp[k++] = A[j++];
    }
    for (i = start, k = 0; i <= end; i++, k++) {
        A[i] = tmp[k];
    }
}

void mergeSort(int A[], int start, int end) {
    if (start < end) {
        int mid = (start + end) / 2;
        mergeSort(A, start, mid);
        mergeSort(A, mid + 1, end);
        merge(A, start, mid, end);
    }
}

void mergeTwoArrays(int A[], int N, int k) {
    mergeSort(A, 0, k);
    mergeSort(A, k + 1, N - 1);
    int i = 0, j = k + 1;
    while (i < j && j < N) {
        if (A[i] <= A[j]) {
            i++;
        } else {
            int tmp = A[j], l = j;
            while (l > i) {
                A[l] = A[l - 1];
                l--;
            }
            A[i] = tmp;
            i++;
            j++;
        }
    }
}

其中，`merge`函数是归并排序中的合并函数，`mergeSort`函数是归并排序，`mergeTwoArrays`函数是将两个有序子数组合并的函数，其中k是两个子数组的分界点，N是数组的长度。