1

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

Johnyb
  • 980
  • 1
  • 12
  • 27
  • Perhaps you should move this to [codereview.se]. – 001 Dec 13 '16 at 15:33
  • Look at how they do it here: http://quiz.geeksforgeeks.org/merge-sort/ – NathanOliver Dec 13 '16 at 15:34
  • Note VLA is not valid c++ code – Slava Dec 13 '16 at 15:35
  • @Slava what do u mean by VSA? ,@NathanOliver i know they create two arrays , but i was wondering if 1 would be enough . COnsidering i do not have to copy elements to those 2 arrays. – Johnyb Dec 13 '16 at 15:36
  • @NathanOliver thx fixed :) Johnyb: in C++ you cannot use variable for array size. – Slava Dec 13 '16 at 15:38
  • @Slava hm , g++ and -Wall -Pedantic does not throw any warning – Johnyb Dec 13 '16 at 15:40
  • @Johnyb that's gcc extention, which does not make that legal c++ code, details here http://stackoverflow.com/questions/1887097/why-arent-variable-length-arrays-part-of-the-c-standard – Slava Dec 13 '16 at 15:42

1 Answers1

0

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.

Community
  • 1
  • 1
Виталик Бушаев
  • 801
  • 10
  • 26