C代码中的CRLS归并排序边界代码理解

Question

void merge(int A[], int p, int q, int r) {
    int *tmpL, *tmpR;
    int boundary;
    int n1, n2;
    int i, j, k;

    n1 = q - p + 1;
    n2 = r - q;

    tmpL = (int *)malloc(sizeof(int) * (n1 + 1));
    tmpR = (int *)malloc(sizeof(int) * (n2 + 1));

    for (i = 0; i < n1; i++)
        tmpL[i] = A[p + i];
    for (j = 0; j < n2; j++)
        tmpR[j] = A[q + j + 1];

    boundary = tmpL[n1 - 1] > tmpR[n2 - 1] ? tmpL[n1 - 1] + 1 : tmpR[n2 - 1] + 1;
    tmpL[n1] = boundary;
    tmpR[n2] = boundary;

    i = 0;
    j = 0;

    for (k = p; k <= r; k++) {
        if (tmpL[i] <= tmpR[j]) {
            A[k] = tmpL[i];
            i++;
        } else {
            A[k] = tmpR[j];
            j++;
        }
    }

    free(tmpL);
    free(tmpR);
}
void merge_sort(int A[], int p, int r) {
    int q;

    if (p < r) {
        q = (p + r) / 2;
        merge_sort(A, p, q);
        merge_sort(A, q + 1, r);
        merge(A, p, q, r);
    }
}

我无法完全理解这个无限边界代码 boundary = tmpL[n1 - 1] > tmpR[n2 - 1] ？ tmpL[n1 - 1] + 1 : tmpR[n2 - 1] + 1;

谢谢 /image/UmyUg.png (蓝色圈出)

这是一个条件语句，A> B？ C:D。如果 A> B 为真，则计算 C，否则计算 D。但我仍然不明白边界部分。这是否与添加两个 while 循环来处理其中一半有剩余元素并将它们追加到新数组末尾相同？

如果我不将它们初始化为无限边界，它们可能会给我一个段错误。

Answer 1

该代码对 mergesort 使用了通用方法其中副本由两个子数组组成，末尾有一个额外元素，设置为大于两个数组最大值的值。

声明boundary = tmpL[n1 - 1] > tmpR[n2 - 1] ? tmpL[n1 - 1] + 1 : tmpR[n2 - 1] + 1;尝试计算值 boundary为 1 加上 tmpL 的最大值或 tmpR取决于哪个更大。它使用了一个三元表达式，大致相当于这样写:

    if (tmpL[n1 - 1] > tmpR[n2 - 1])
        boundary = tmpL[n1 - 1] + 1;
    else
        boundary = tmpR[n2 - 1] + 1;

然后合并循环可以使用单个测试 k <= r停止循环和i将等于 n1和 j将等于 n2什么时候k达到 r + 1 .

这种方法在很多方面都是错误的:

• 如果任一子数组包含最大值INT_MAX , boundary 的计算将溢出并导致未定义的行为。即使溢出不会导致致命的副作用，boundary 的值将毫无意义，导致不正确的结果或其他未定义的行为。
• 数组边界测试很简单，比这个不完整的变通方法简单得多。
• 此方法需要分配和复制两个数组，而右半部分不需要保存，因为 merge不会覆盖尚未复制的值。

在我看来，根本不应该教授这种方法。

这是一个没有这些缺点的替代实现:

void merge(int A[], int p, int q, int r) {
    int *tmpL;
    int n1, n2;
    int i, j, k;

    // It is much simpler to consider q to point to the first element of
    // the second subarray and r to point after the last element of that array.
    q++;
    r++;

    n1 = q - p;  // number of elements in the left sorted subarray
    n2 = r - q;  // number of elements in the right sorted subarray

    tmpL = (int *)malloc(sizeof(int) * n1);
    if (tmpL == NULL) {
        // Report this fatal error or fall back to a different 
        // algorithm that does not require allocation, such as
        // heapsort or insertion sort.
        return;
    }
    // Make a copy of the left subarray as elements may be overwritten in the loop.
    for (i = 0; i < n1; i++) {
        tmpL[i] = A[p + i];
    }

    // Merge the elements of the subarrays:
    // - if all elements of the left array have been merged, 
    //   the remaining elements of the right subarray are already in place
    // - if k has reached r, all elements have been sorted
    for (i = j = 0, k = p; i < n1 && k < r; k++) {
        if (j >= n2 || tmpL[i] <= A[q + j]) {
            // Take the element from tmpL if the right subarray is empty
            //    or if it is no greater than the next one from the right subarray.
            A[k] = tmpL[i];
            i++;
        } else {
            // Otherwise take the element from the right subarray.
            A[k] = a[q + j];
            j++;
        }
    }
    free(tmpL);
}