Can someone help me figure out a memory problem with my algorithm?

[Argus]

I asked this question in another C++ board, but I didn't really understand what they told me. So I would like to ask in here to see what I can do. I'm reading CLRS, I'm in chapter two in the section about Merge Sort, usually when I get through a chapter I implement the algorithms that are explained. I chose to use C++ because it is a language I'm not really adept at, and because I really want to get good at it. However, I'm having trouble figuring out why my merge sort has bad_alloc error. I assume my recursion is breaking something, or my merge function simply reserves too much memory, but I'm really new at memory management and the only time I saw it I didn't understand how it worked. I should also mention that it works great, up until I have more than three elements in an array.

Here's my .h file:

#ifndef SORTING_H
#define SORTING_H
#include <vector>

std::vector<int> merge_sort(std::vector<int> array, int pos, int size);
std::vector<int> merge(std::vector<int> array, int init, int mid, int size);

#endif 

Anyway this is my code, this is my merge function:

#include <vector>
#include <climits>
#include "sorting.h"

using std:vector;
{
	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.push_back(INT_MAX);
        right.push_back(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;
}

This is my merge sort:

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, size/2);
		merge(array, pos, size/2, size);
		return array;
	}
}

Finally, here is my main:

#include <iostream>
#include <vector>
#include "sorting.h"

using std::vector;
using std::cout;
using std::endl;

int main(int argc, char * argv[])
{
	vector<int> array{10,2,4,5,11,8,3};
	array = merge_sort(array,0,array.size());

	for(int i = 0; i < array.size(); i++)
	{
		cout << array[i] << endl;
	}
	return 0;
}

[coder777]

In your merge() function:
Line 19 will crash due to the out of bounds operation.
Line 20 is certainly not what you want to do.

[Argus]

Yeah, I missed that, so I changed it to:

left.push_back(INT_MAX);
right.push_back(INT_MAX);

Nonetheless, I still get the same error I was having before and I can't figure out where I'm allocating memory improperly. This is what it says:

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

[coder777]

lines 28/33 may also go out of bounds. if you'd provide the code to reproduce the problem it'd be easier to help you.

You might also take a look here:

https://en.wikipedia.org/wiki/Merge_sort

[Argus]

Ok, I included the .h file and my main in the first post. I'm sorry if I didn't put it earlier, I haven't asked questions in a while.

[coder777]

The reason for the crash is that at one point in merge(...) a1_size becomes negative (init > mid). Because merge_sort(...) line 11: pos > size/2


Again merge(...) lines 32/37: i/j will probably be out of bounds.

Further more: Since you pass array by value as a copy and in merge_sort(...) you do not assign the return value, at the end you get an unchanged array.

[Argus]

I see, thank you very much for your help. I will proceed to fix it then. Thanks again.