c++ - Mergesort:动态分配大小仅在运行时已知的数组

Question

我正在上算法课，并试图在 C++ 中实现合并排序。我试图存储左右子数组，但意识到我无法这样做，因为我无法在运行时初始化大小。有没有办法解决这个问题，或者我是否错误地进行了排序过程？我在下面列出了我所拥有的。

我也在努力避免 vector ，因为那太明显和容易了。

void merge(int *arr, int left, int mid, int right)
{
    int size1 = mid - left + 1;
    int size2 = right - mid;

    int leftArr[size1];
    int rightArr[size2];
    ....

}
void mergeSort(int *arr, int left, int right)
{
    if (left < right)
    {
        int mid = (left + right) / 2;
        mergeSort(arr, mid+1, right);
        mergeSort(arr, left, mid);
        merge(arr, left, mid, right);
    }
}

Answer 1

在我看来，使用 vector 会容易得多，这就是 C++。但是，如果您只是为了学习而这样做，那么您可以像建议的那样动态分配数组。

int *leftArr = new int[size1];
int *rightArr = new int[size2];

//do stuff

//don't forget to free your memory

delete [] leftArr;
delete [] rightArr;