bad_alloc exception while implementing the merge sort for larger arrays

Question

I'm implementing the merge sort algorithm using C++. An exception(bad_alloc) is raised, while sorting larger arrays. Since i'm new to C++ i have no idea about how to get rid of this error. The answer i'm willing is not handling the exception, but the reason.

Here's my main method where i initially calls merge_sort function.

int *arr;

int main(){
        int limits[2]={10,10000000};            //numbers of elements that should be in an array at each iteration

        for(int l=0;l<sizeof(limits)/sizeof(*limits);l++){
                cout<<"\n"<<endl;
                arr=new int[limits[l]];
                for(int cnt=0;cnt<limits[l];cnt++){                             //creating the random array using random numbers
                        int temp=rand()%2147483647;
                        arr[cnt]=temp;
                }
                clock_t t;
                t=clock();
                cout<<"\nNumber of elements  :  "<<limits[l]<<endl;

                merge_sort(0,limits[l]-1);                              //calling the merge sort function
                cout<<endl;
                t=clock()-t;
                cout<<"The time taken :  "<<t<<endl;
                delete[] arr;
        }
        cin.get();
return 0;
}

Up to 1000000 elements this works fine. I'm having the trouble when sorting the array of size 10000000.

Here's the full code for test purposes.

#include<iostream>
#include<string.h>
#include<limits>
#include<time.h>
#include<stdlib.h>

using namespace std;
void merge_sort(int i,int j);
void merge(int i,int temp,int j);

int *arr;

//main method
int main(){
        int limits[2]={10,10000000};            //numbers of elements that should be in an array at each iteration
        for(int l=0;l<sizeof(limits)/sizeof(*limits);l++){
                cout<<"\n"<<endl;
                arr=new int[limits[l]];
                for(int cnt=0;cnt<limits[l];cnt++){                             //creating the random array using random numbers
                        int temp=rand()%2147483647;
                        arr[cnt]=temp;
                }
                clock_t t;
                t=clock();
                cout<<"\nNumber of elements  :  "<<limits[l]<<endl;

                merge_sort(0,limits[l]-1);                              //calling the merge sort function

                t=clock()-t;
                cout<<"The time taken :  "<<t<<endl;
                delete[] arr;
        }
        cin.get();
return 0;
}


//method implementing the merge sort algorithm
void merge_sort(int i,int j){
        if(i<j){
                int temp=(i+j)/2;
                merge_sort(i,temp);
                merge_sort(temp+1,j);
                merge(i,temp,j);
        }
        return;
}


//method implementing the merge algorithm
void merge(int i,int temp,int j){
        int n1=temp-i+2;                                    //calculating the sub array lengthes
        int n2=j-temp+1;
        int *L=NULL;
        int *R=NULL;
        L=new int[n1];                                      //dynamically initializing the sub left and right hand side arrays
        R=new int[n2];

        for(int x=0;x<n1-1;x++){
                L[x]=arr[i+x];
        }
        for(int y=0;y<n2-1;y++){
                R[y]=arr[temp+y+1];
        }
        L[n1-1]=numeric_limits<int>::max();                 //adding the largest possible integer to the end of each array
        R[n2-1]=numeric_limits<int>::max();
        int a=0;
        int b=0;
        for(int k=i;k<=j;k++){                              //merging the two sub arrays
                if(L[b]>R[a] ){
                        arr[k]=R[a];
                        a++;
                }
                else{
                        arr[k]=L[b];
                        b++;
                }
        }
}

It's better if someone can give me the reason behind this rather than a fix. Thanks!

Answer 1

Your merge function has a memory leak, and a very big one:

L = new int[n1];    
R = new int[n2];

The memory is never deallocated. If you're coming from a language such as Java or C#, you see that C++ works differently. There is no automatic garbage collection, and using new[] in C++ requires you use delete[] at some point, else you get a memory leak.

But a better solution would be to replace those lines with this:

#include <vector>
//...
// Remove the int *L and int *R declarations.
//
std::vector<int> L(n1);
std::vector<int> R(n2);

You should always think vector first over using new[]/delete[] to avoid these types of memory errors.

Once you make those changes, the program will complete, but takes a while (at least it did with Visual Studio 2013 in debug mode).

In release mode, the time took for 10000000 was 3,300 ms.

Edit: For an experiment, I used the following code to see what would happen if the vector was moved out of the function, and just reused:

std::vector<int> L;
std::vector<int> R;

void merge(int i, int temp, int j){
    int n1 = temp - i + 2;  
    int n2 = j - temp + 1;

    L.resize(n1);
    R.resize(n2);
//...
}

So I made the vectors global. The amount of time it took was closer to 2,000 ms, so approximately 1,000 ms faster. The advantage is the usage of resize to resize the vectors as opposed to redeclaring them, or using new[]/delete[] multiple times.