В коде используется общий подход для 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);
}