CRLS合并排序边界代码对C代码的理解

该代码使用一种通用方法来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);
}