c++ - 合并排序不起作用？

Question

我在让我的合并排序函数与我的教授给我的规范一起工作时遇到了一些问题。一直盯着 VS 和谷歌看，试图找出这个人。

提供的算法:

数组函数.h

template<class T>
void printArray(T arr[], int numElements)
{
    cout << "(";

    for (int i = 0; i < numElements; i++)
    {

        cout << arr[i];

        if (i < numElements - 1)
            cout << ", ";
    }

    cout << ")" << "\n\n";
}

template <class T>
void setArray(T to[], T from[], int size)
{
    for (int i = 0; i < size; i++)
        to[i] = from[i];
}

template <class T>
void setArray(T to[], T from[], int size1, int size2)
{
    int size = size1;
    if (size2 < size1) size = size2;

    setArray(to, from, size);
}

主要

const int NUM = 5;

int originalArray[NUM] = { 4, 2, 5, 3, 1 };
int newArray[NUM];

cout << "Original:\n";
printArray(originalArray, NUM); //prints an array with formatting

// Merge Sort
setArray(newArray, originalArray, NUM); //set's newArray to the same values of originalArray
mergeSort(newArray, 0, NUM - 1);

cout << "Merge Sort:\n";
printArray(newArray, NUM);

pause();

运行 main 时的输出是:

原文:(4, 2, 5, 3, 1 )

合并排序:(0, 0, 0, -33686019, 1)

合并:

template <class T>
void merge(T L[], int lowerBound, int mid, int upperBound)
{
    // Get size for new arrays
    int size1 = mid - lowerBound;
    int size2 = upperBound - mid;

    // Create Temporary Arrays
    T * tmp1 = new T[size1 + 1]();
    T * tmp2 = new T[size2 + 1]();


    // Populate both arrays from original
    for (int i = 0; i < size1; i++)
        tmp1[i] = L[lowerBound + i];

    for (int j = 0; j < size2; j++)
        tmp2[j] = L[mid + j];

    tmp1[size1] = numeric_limits<T>::max();
    tmp2[size2] = numeric_limits<T>::max();

    int i = 0;
    int j = i;

    for (int k = lowerBound; k < upperBound; k++)
    {
        if (tmp1[i] <= tmp2[j])
        {
            L[k] = tmp1[i];
            i++;
        }
        else
        {
            L[k] = tmp2[j];
            j++;
        }
    }

    delete[] tmp1;
    delete[] tmp2;
}

合并排序:

template<class T>
void mergeSort(T L[], int lowerBound, int upperBound)
{
    if (lowerBound < upperBound)
    {
        int mid = (lowerBound + upperBound) / 2;

        mergeSort(L, lowerBound, mid);
        mergeSort(L, mid + 1, upperBound);

        merge(L, lowerBound, mid, upperBound);
    }
}

那么...我做错了什么？非常感谢朝着正确方向前进。

Answer 1

这是一个简单的失误。

T * tmp1 = new T[size1 + 1]();
...
tmp1[size1 + 1] = numeric_limits<T>::max();
           ^^^

数组索引从 0 到 n-1，而不是 n。