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

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;

谢谢 https://i.stack.imgur.com/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来停止循环，当k达到r + 1时，i将等于n1j等于n2。

这种方法在许多方面都被打破了：

• 如果任一子数组包含最大值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);
}

Answer 2

merge() 应该合并 A 中两个已经排序的运行，从 A[p] 到 A[q]，以及从 A[q+1] 到 A[r](包括)。创建 TmpL 和 TmpR，每个元素末尾都有 1 个额外元素的空间，用作大于 TmpL 或 TmpR 中任何值的哨兵值。三元语句将边界设置为 TmpL 和 TmpR 中最后一个值中的较大值，然后将 1 加到此值以创建存储在 TmpL 和 TmpR 末尾的哨兵值。这样就无需检查索引"i"或"j"以查看是否已到达 TmpL 或 TmpR 的末尾，在这种情况下，TmpR 或 TmpL 的其余部分将被复制回 A[]。

对于大多数编程语言，代码可以只将 boundary 设置为 INT_MAX 或包含文件 limits.h 中的其他最大值之一(对于C++，climits)，而不是使用三元语句：

http://www.cplusplus.com/reference/climits

如果对浮点数或双精度进行排序，则可以将边界设置为无穷大。

分段错误的原因是，如果没有哨兵值，代码可能会超出导致故障的 TmpL 或 TmpR 的末尾。

这种排序方法的一个问题是 A[] 可能已经包含最大可能值，在这种情况下，此方法将失败。对于整数，将 1 加到最大值将换行到最小值。