确定合并排序中边数组的大小

Question

我想实现合并排序。我的代码工作

void merge(int * , int , int , int ); 

void mergeSort(int *arr , int low , int high){ 

    if(low < high){ 
     int mid = (low + high)/2; 
     mergeSort(arr , 0 , mid); 
     mergeSort(arr , mid +1, high); 
     merge(arr , low , mid , high); 
    } 
} 

void merge(int *arr , int low , int mid , int high){ 


    int barr[ high ]; 
    int i  = low; 
    int j  = mid + 1; 
    int index = low; 
    while(i <= mid && j <= high){ 
     if(arr[i] < arr[j]){ 
      barr[index++] = arr[i++]; 
     } 
     else{ 
      barr[index++] = arr[j++]; 
     } 
    } 
    if(i < mid + 1) 
     for(int x = i ; x < mid +1 ; x++) 
      barr[ index++ ] = arr[x]; 

    if(j <= high) 
     for(int y = j ; y < high ; y ++) 
      barr[ index++ ] = arr[y]; 
    for(int z = low ; z < index ; z++){ 
     arr[z] = barr[z]; 
    } 
} 

int main() 
{ 
    int arr[] = { 5 ,6 , 2, 6 ,7 , 5 ,8 ,9}; 
    mergeSort(arr , 0 , 8); 
    for(int i = 0; i < 8 ; i++){ 
     cout << arr[i] << " "; 
    } 
    return 0; 
} 

我有什么难的时间来决定是该行

int barr[high]; 

我怎样才能有效决定这一侧数组的大小？我认为高 - 低将是足够的，但appeareltny它不，当我创建一个大小为1我访问更大的索引元素。有没有办法如何确定它，或者我必须始终创建一个高元素的数组，这会导致大的内存消耗=我的代码无效。

感谢

Answer 1

正如在评论中指出，VLAs aren't valid in C++。 至于你的问题，如果你想合并数组的一部分索引从low到high，那么你需要确切的high - low + 1数组大小。