合并排序 - 堆栈损坏错误

Question

我在C++中编写了一个基本的合并排序代码。当我在函数merge（）中运行下面的代码时，我得到变量b的堆栈损坏异常。我无法弄清楚我做错了什么。任何帮助非常感谢！

这是我的代码：

template <class T> 
class mSort 
{ 
    void mergeSort(T *a, int low, int high); 
    void merge(T *a, int low, int mid, int high); 
public: 
    mSort(T* a, int size); 
}; 

template<class T> 
mSort<T>::mSort(T *a, int size) 
{ 
    mergeSort(a, 0, size); 
} 
template<class T> 
void mSort<T>::mergeSort(T *a, int low, int high) 
{ 
    int m; 
    if (low < high) 
    { 
     m = (low + high)/2; 
     //printf("mergeSort:low[%d], mid [%d], high [%d]\n", low, m, high); 
     mergeSort(a, low, m); 
     mergeSort(a, m+1, high); 
     merge(a, low, m, high); 
    } 
} 

template<class T> 
void mSort<T>::merge(T *a, int low, int mid, int high) 
{ 
    int b[20]; 
    int i = low, j = mid + 1, k = 0; 

    while (i <= mid && j <= high) { 
     if (a[i] <= a[j]) 
      b[k++] = a[i++]; 
     else 
      b[k++] = a[j++]; 
    } 
    while (i <= mid) 
     b[k++] = a[i++]; 

    while (j <= high) 
     b[k++] = a[j++]; 

    k--; 
    while (k >= 0) { 
     a[low + k] = b[k]; 
     k--; 
    } 
} 

输入数组： INT A [20];

#define prep_intput_array(a,n)\ 
for (int i = 0; i < n; i++)\ 
{\ 
    a[i] = rand() % 65535;\ 
}\ 

调用合并排序过程是这样的：

mSort<int> m1(a, 20); 

代码是基于合并排序在这个link

Answer 1

高传递与数组中最高的指数大小-1，但你已经通过尺寸大于阵列中的最高索引，因此您可能会收到错误。

Answer 2

你high是数组的大小，假设20是指从开始的数组索引0至19。

看起来你试图访问b[20] - >这是数组的元素21st。显然是出界了。

下面的代码看起来很怀疑我。它应该检查j<high（不j<=high）

while (i <= mid && j <= high) { 

同样的，下面的代码：

while (j <= high) 
     b[k++] = a[j++];