合并排序中数组的索引号有问题吗？

Question

所以我试图在 C++ 中实现归并排序，这个版本使用了 space 复杂度的 O(n)。
该算法是使用 "Foundation of Algorithms".
一书中的伪代码编写的我认为在函数 merge2.
中使用索引时存在一些错误以_tmp结尾的变量用于操作数组U，不带_tmp的变量用于操作数组S.

#include <iostream>

int n = 8;
int S[8] = { 0, };

void mergeSort2(int low, int high);
void merge2(int low, int mid, int high);

void mergeSort2(int low, int high) {
    int mid;
    if (low < high) {
        mid = (low + high) / 2;
        mergeSort2(low, mid);
        mergeSort2(mid + 1, high);
        merge2(low, mid, high);
    }
}

void merge2(int low, int mid, int high) {
    int i, j, k;
    int i_tmp, j_tmp, k_tmp;
    int high_tmp = high - low;
    int low_tmp = 0;
    int mid_tmp = high / 2;
    i_tmp = low_tmp; j_tmp = mid_tmp + 1; k_tmp = low_tmp;
    i = low; j = mid + 1; k = low;
    int* U = new int[high_tmp + 1];
    while (i <= mid && j <= high) {
        if (S[i] < S[j]) {
            U[k_tmp] = S[i];
            i++;
            i_tmp++;
        }
        else {
            U[k_tmp] = S[j];
            j++;
            j_tmp++;
        }
        k++;
        k_tmp++;
    }
    if (i_tmp > mid_tmp) {
        //move S[j] through S[high] to U[k] through U[high-1]
        for (int r = j, s = k_tmp; r < high, s < high_tmp; r++, s++) {
            U[s] = S[r];
        }
    }
        else {
        //move S[i] through S[mid] to U[k] through U[high-1]
        for (int r = i, s = k_tmp; r < mid, s < high_tmp; r++, s++) {
            U[s] = S[r];
        }
    }
    //move U[low] through U[high] to S[low] through S[high-1]
    for (int r = low_tmp, s = low; r < high_tmp, s < high; r++, s++) {
        S[s] = U[r];
    }
    delete U;
}

int main() {
    std::cout << "Enter the elements of the array S (size : " << n << ") : ";
    for (int i = 0; i < n; i++) {
        std::cin >> S[i];
    }
    mergeSort2(0, n);
    std::cout << std::endl;
    std::cout << "Result of array S sorted in an ascending order : ";
    for (int i = 0; i < n; i++) {
        std::cout << S[i] << "  ";
    }
    std::cout << std::endl << std::endl;
    return 0;
}

Answer 1

正如评论中所指出的，问题在于您的 for 循环的测试条件使用逗号运算符。如cppreference所述：

In a comma expression E1, E2, the expression E1 is evaluated, its result is discarded ... before evaluation of the expression E2 begins ...

因此，在循环中：

for (int r = j, s = k_tmp; r < high, s < high_tmp; r++, s++) {
   //...

r < high 表达式 从未使用过 并且只有当 s < high_tmp 表达式的计算结果为 false.[=19 时循环才会结束=]

如果你希望循环在either表达式为假时结束，你需要用&&（逻辑AND运算符）将两个测试结合起来：

for (int r = j, s = k_tmp; r < high && s < high_tmp; r++, s++) {
   //...

合并排序中数组的索引号有问题吗？

Is there something wrong with the index number of array in merge sort?

c++

arrays

indexing

mergesort