归并排序输出错误

Question

我试图在c++中使用模板函数编写合并排序算法。输出接近但不正确。当我给函数一个数组[7,6,4,8,1,2,3]时，它返回[1,1,2,2,2,8]。我特别认为问题出在归并函数而不是归并排序函数。任何帮助都将非常感激。下面是我的代码:

template <class T1>
void mergeSort(T1 array[], int lower, int upper)
{
    if (lower < upper)
    {
        int middle = (lower + upper) / 2;
        mergeSort(array, lower, middle);
        mergeSort(array, middle + 1, upper);
        merge(array, lower, middle, upper);
    }
}
template <class T1>
void merge(T1 array1[], int lower, int middle, int upper)
{
    int i = 0,
        j = 0,
        k = 0;
    int size1 = middle - lower + 1;
    int size2 = upper - middle;
    T1* temp1 = new T1[size1];
    T1* temp2 = new T1[size2];
    for (int i = 0; i < size1; i++)
    {
        temp1[i] = array1[lower + i];
    }
    for (int j = 0; j < size2; j++)
    {
        temp2[j] = array1[middle + 1 + j];
    }
    while (i < size1 && j < size2)
    {
        if (temp1[i] < temp2[j])
        {
            array1[k] = temp1[i];
            i++;
        }
        else
        {
            array1[k] = temp2[j];
            j++;
        }
        k++;
    }
    if (i == size1)
    {
        while (j < size2)
        {
            array1[k] = temp2[j];
            k++;
            j++;
        }
    }
    else
    {
        while (i < size1)
        {
            array1[k] = temp1[i];
            k++;
            i++;
        }
    }
}
int main(){
     int a[] = { 7, 6, 4, 8, 1, 2, 3 };
     mergeSort(a, 0, 6);
}

输出:

1 1 2 2 3 3 8

Answer 1

在你的merge函数你不应该初始化k为0，因为它会在错误的地方写合并的结果。相反，您应该将k初始化为lower。因为那是你要排序的部分的起始索引