由于堆栈溢出，迭代合并排序的 C++ 实现在输入大时崩溃

Question

我对堆栈溢出没有太多经验，我认为它们是由超过一定递归深度的递归函数引起的，为什么它们会出现在合并排序的这种迭代实现中!

    #include<iostream>
    #include <stdlib.h>
    #define SIZE 3000000

    int L[2500002];
    int R[2500002];

    using namespace std;

    int min(int a, int b) {
        return !(b<a) ? a : b;
    }

    void Merge(int data[], int p, int q, int r)
    {
        if (q >= SIZE)q = (r + p) / 2;
        int sizeL = q - p + 2;
        int sizeR = r - q + 1;

        for (int i = 0; i < sizeL - 1; i++)
            L[i] = data[i + p];
        for (int i = 0; i < sizeR - 1; i++)
            R[i] = data[i + q + 1];

        int max;
        if (L[sizeL - 2]>R[sizeR - 2])
            max = L[sizeL - 2] + 1;
        else
            max = R[sizeR - 2] + 1;
        L[sizeL - 1] = R[sizeR - 1] = max;

        int indexL = 0, indexR = 0;
        for (int i = p; i <= r; i++){
            if (L[indexL] <= R[indexR]){
                data[i] = L[indexL];
                indexL++;
            }
            else{
                data[i] = R[indexR];
                indexR++;
            }
        }


    }

    void MergeSort(int data[], int p, int r)
    {
        for (int i = 1; i< SIZE; i *= 2)
            for (int j = 0; j < SIZE; j += 2 * i)
                Merge(data, j, j + i - 1, min((j + 2 * i - 1), SIZE - 1));
    }
    /*****************************************************************************/

    bool IsSorted(int data[], int size)
    {
        int i;

        for (i = 0; i<(size - 1); i++)
        {
            if (data[i] > data[i + 1])
                return false;
        }
        return true;
    }

    int main()
    {
        int data[SIZE];
        for (int i = 0; i < SIZE; i++)
            data[i] = rand();
        MergeSort(data,0,SIZE-1);
        if(IsSorted(data, SIZE))
            cout << "Sorted correctly";
        else
            cout << "incorrect sorting";
        getchar();
        return 0;
    }

Answer 1

int main()
{
    int data[SIZE];
    ...

声明堆栈上的数组。堆栈大小有限制。它因操作系统和配置而异，但很容易小于 12 MB，即您请求的数量(假设为 32 位整数)。尝试在堆上分配数组，而不是使用 std::vector。

编译器不可能警告您这个问题，因为堆栈大小是由操作系统在加载程序时设置的。您可以重新配置您的操作系统以默认使用一个小堆栈，并且之前运行的程序会突然开始溢出。

如果您有兴趣了解有关操作系统如何检测堆栈溢出的更多信息，请查看虚拟内存、MMU 和保护页。