Thread: My merge sort has a bad alloc error

Hello, I'm having a problem with a C++ merge sort I implemented. I'm still fairly new to the language and I don't really know about memory management as much as I'd like. This is my first time running into an error of this sort, and I'm not sure how to fix it. Can someone help me out?

The error it throws is this:

terminate called after throwing an instance of 'std::bad_alloc'
what(): std::bad_alloc
Aborted



This is my merge function:

Code:

vector<int> merge(vector<int> array, int init, int mid, int size)
{
	int i;
	int j;
	int a1_size = mid - init + 1;
	int a2_size = size - mid;
	vector<int> left(a1_size);
	vector<int> right(a2_size);


	for(i = 0; i < a1_size; i++)
	{
		left[i] = array[init + i];
	}


	for(j = 0; j < a2_size; j++)
	{
		right[j] = array[mid + j];
	}
	left[a1_size + 1] = INT_MAX;
	left[a2_size + 1] = INT_MAX;
	i = 0;
	j = 0;


	for(int k = 0; k < array.size(); k++)
	{
		if(left[i] <= right[j])
		{
			array[k] = left[i];
			i++;
		}
		else
		{
			array[k] = right[j];
			j++;
		}
	}
	left.clear();
	right.clear();
	return array;
}

And this is my merge sort:

Code:

vector<int> merge_sort(vector<int> array, int pos, int size)
{
	if(size == 1)
	{
		return array;
	}
	else
	{
		merge_sort(array, pos, size/2);
		merge_sort(array, size/2+1, size/2);
		merge(array, pos, size/2, size);
		return array;
	}
}

I think it is happening because of the recursive calls, because it works well up to 3 element arrays.