遞歸合併排序，大數組的分段錯誤

Question

我已經遞歸地實現了合併排序。它工作到一定大小的排序數組，然後它崩潰與「分段錯誤」。在Intel Xeon 16GB上，最大浮點數組大小爲17352，對於int數組而言較高，對於雙數組較低。在AMD A10,16GB上，浮點數的限制是2068。顯然存在內存問題。我爲數組做的其他排序算法（非遞歸）適用於高達〜2e6。編譯器是GCC 4.4.7。我如何改進這種合併排序，以便適用於更大的數組？

#include <iostream> 
#include <stdlib.h> 
#include <cmath> 
#include <vector> 
using namespace std; 

// -------------------------------------------------------- 
// merge 2 subarrays of 1 array around its middle im 
template <class C> 
void merge(C* arr, int ilow, int imid, int ihigh) 
{ 
vector<C> temp; // array seg faults earlier than vector 
for(int i=ilow; i<=ihigh; i++) temp.push_back(arr[i]); // copy array 

int i1=ilow, i2=imid+1, ai=ilow; // starting positions 

while(i1<=imid && i2<=ihigh) // compare 1st and 2nd halves 
{ 
    if(temp[i1]<=arr[i2]) 
    { 
     arr[ai] = temp[i1]; 
     i1++; // leave smaller val behind 
    } 
    else 
    { 
     arr[ai] = temp[i2]; 
     i2++; // leave smaller val behind 
    } 
    ai++; // move forward 
} 

if(i2>ihigh) while(i1<=imid) // if 2nd is done, copy the rest from 1st 
{ 
    arr[ai] = temp[i1]; 
    i1++; 
    ai++; 
} 

if(i1>imid) while(i2<=ihigh) // if 1st is done, copy the rest from 2nd 
{ 
    arr[ai] = temp[i2]; 
    i2++; 
    ai++; 
} 

} // merge() 



// -------------------------------------------------------- 
// merge sort algorithm for arrays 
template <class C> 
void sort_merge(C* arr, int ilow, int ihigh) 
{ 

if(ilow < ihigh) 
{ 
    int imid = (ilow+ihigh)/2; // get middle point 
    sort_merge(arr, ilow, imid); // do 1st half 
    sort_merge(arr, imid+1, ihigh); // do 2nd half 
    merge(arr, ilow, imid, ihigh); // merge 1st and 2nd halves 
} 

return; 
} // sort_merge() 



/////////////////////////////////////////////////////////// 
int main(int argc, char *argv[]) 
{ 
// crashes at 17353 on Intel Xeon, and at 2069 on AMD A10, both 16Gb of ram 
const int N=17352+0; 
float arr[N]; // with arr[double] crashes sooner, with arr[int] crashes later 

// fill array 
for(long int i=0; i<N; i++) 
{ 
    //arr[i] = rand()*1.0/RAND_MAX; // random 
    arr[i] = sin(i*10)+cos(i*10); // partially sorted 
    //arr[i] = i; // sorted 
    //arr[i] = -i; // reversed 
} 

sort_merge(arr, 0, N-1); 

return 0; 
} 

Answer 1

下，所有的本身，就足以引起分段錯誤，如果N是足夠大的，由於臭名昭著stack overflow。如果不是，填充陣列應該。

int main(int argc, char *argv[]) 
{ 
    // crashes at 17353 on Intel Xeon, and at 2069 on AMD A10, both 16Gb of ram 
    const int N=17352+0; 
    float arr[N]; 
} 

的原因是局部變量往往會在堆棧中分配，但堆棧大小的限制，不適合大規模的內存分配。如果你不是做

float *arr = new arr[N]; // probably should be unique_ptr instead.... 

或

std::vector<float> arr(N); 

你不會有任何問題，因爲這兩種方法在堆中分配內存。

Answer 2

考慮要複製的陣列方式：

vector<C> temp; // array seg faults earlier than vector 
for(int i=ilow; i<=ihigh; i++) temp.push_back(arr[i]); // copy array 

完成該操作後，temp包含ihigh - ilow + 1值，這是從temp[0]到temp[ihigh - ilow]訪問。這意味着temp中的所有值都被-ilow抵消，而arr抵消。

但是您的代碼的其餘部分的訪問temp與源陣列的索引，例如：

if(temp[i1]<=arr[i2]) // i1 isn't a valid index into temp, should be (i1 - ilow) 

因此崩潰。在temp中使用正確的偏移量時，您的代碼似乎爲work correctly。