为什么当对数组大小为10^6和元素大小为10^9而不是合并排序运行快速排序时，我面临sigsegv错误?

Question

我尝试了迭代的方式，选择pivot元素作为数组的最后一个元素。我在Hacker Earth上执行了它，这引发了sigsegv错误，其中数组大小范围从1到10^6，数组元素大小从1到10^9。当我尝试归并排序时，它做得很有效，甚至没有引起错误。这是怎么发生的?下面是实现的代码:

// An iterative implementation of quick sort        /* working*/
#include <iostream>
using namespace std;
void swap ( long int &a, long int &b )
{
    long int t = a;
    a = b;
    b = t;
}
int partition (int arr[],long int l,long int h)
{
    long int x = arr[h];
    long int i = l;
    long int j=h-1;
    while(i<j){
        if(arr[i]<x){
            i++;
        }
        if(arr[j]>x){
            j--;
            continue;
        }
        if(arr[i]>x&&arr[j]<x){
            swap(arr[i],arr[j]);
            i++;
            j--;
        }
    }
    swap(arr[i],arr[h]);
    return i;
}
void quickSortIterative (int arr[], int l, long int h)
{
    int stack[2];
    int top = -1;
    stack[ ++top ] = l; 
    stack[ ++top ] = h; 
    while ( top >= 0 )
    {
        h = stack[ top-- ];
        l = stack[ top-- ];
        long int p = partition( arr, l, h );
        if ( p-1 > l )
        {
            stack[ ++top ] = l;
            stack[ ++top ] = p - 1;
        }
        if ( p+1 < h )
        {
            stack[ ++top ] = p+1;
            stack[ ++top ] = h;
        }
    }
}
int main()
{
    long int N;
    cin>>N;
    long int i,j;
    int arr[N];
    for(i=0;i<N;i++){
        cin>>arr[i];
    }
    quickSortIterative( arr, 0, N - 1 );
    for ( i = 0; i < N; ++i ){
        cout<<arr[i]<<" ";
    }
    return 0;

}

Answer 1

stack[2]只有两个整数的空间，但是代码将两个以上的值"压入"堆栈。考虑第一个循环p-1> 1 &&p + 1 & lt;H，在这种情况下top增加4倍。你可以将堆栈设置为vector或stack，使用与push和pop类似的方法来存储和加载值。

int arr[N]对于大N也会失败。由于这是c++，请考虑使用:

int * arr = new int[N];

你需要删除main结尾的[]arr

Answer 2

在局部变量中分配大数组肯定会触发堆栈溢出—在典型的执行环境中，堆栈根本不能处理这些事情。

你需要在堆上分配数组;例如通过使用std::vector。您的代码也将更加可移植，因为可变长度数组不是c++标准的一部分。