Deciding the size of the side array in merge sort

Question

I am trying to implement merge sort. My code works

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;
}

What i have hard time to decide is this line

int barr[high]; 

How can i effective decide the size of this side array? I thought high - low would be enough but appeareltny its not , bcs when i create arary of size 1 i access the elements on bigger index. Is there a way how to decide it or do i have to always create array of high elements which would result in big memory consumation = my code isnt effective.

Thanks

Answer 1

As pointed out in comments, VLAs aren't valid in C++. As for your question, if you want to merge part of array with indexes from low to high, then you need exactly high - low + 1 array size.