Problem passing vectors as parameters to a recursive function

[Basteon]

Hi! I'm writing the mergesort algorithm, theoretically everything is fine in it but when the function gets to call itself the program crashes. I belive that I'm doing something worng when I pass the vector<int> as a parameter to the function.

procedure mergesort(T[1 .. n])
if n is small
then insert(T)
else arrays U[1 .. n div 2], V[1 .. (n+1) div 2]
U <- T[1 .. n div 2]
V <- T[1 + (n div 2) .. n]
mergesort(U); mergesort(V)
merge(T, U, V)

void mergeSort(vector<int>& mass){
	if(mass.size() <= 16)
		sort(mass.begin(),mass.end());
	else {
		vector<int> u,v;
		int size1,size2;
		size1 = div(mass.size(),2).quot;
		size2 = div(mass.size()+1,2).quot;
		u.resize(size1);
		v.resize(size2);
		
		u.assign(mass.begin(),mass.end()-size1);
		v.assign(mass.begin()+size1+1,mass.end());

		mergeSort(u);
		mergeSort(v);
		mass.clear();
		merge(u.begin(),u.end(),v.begin(),v.end(),mass.begin());
	}
};

Can anyone tell me what I'm doing wrong?

[Clinton Portis]

Although I am by no means an algorithms expert, I'll throw in my 2 cents anyway.. maybe I'll get lucky.

In my opinion, I believe there may be a scope issue of the variables declared in line #5. The vectors are pass by value into perhaps a huge stack of numerous calls to the mergeSort() function. The final resulting exit case has nothing to return and thusly destroys the variables upon function completion.

I believe the u & v vectors should be declared outside of the scope of the function (or passed in as an argument if your function and returned, if your function was not void) This will allow the subsequent recursive calls to mergeSort() to directly affect the vectors in memory... because when your recursive functions calls eventually resolve to the exit case (line #3), it's just a merged u or v vector.. which was destroyed by the previous function call, and will be destroyed again at exit case function completion.

**Afterthought: maybe you could just try passing the u & v vectors in by reference in line #5 and see if that works

[Basteon]

The u and v vectors are the 2 halfs of the mass vector. Each time when the function would call itself they would be different depending on the what part of the previous vector was passed into. Declaring them outside the function is pointless.

When I try to compile it i get the "Debug Assertion Failed!" error. Here is the screenshot, maybe this would of some help.

[Basteon]

I have foundout what the problem was. I forgot to resize the mass vetor after clearing it, so when I was merging the u and v vectors there was no place to put the data.
So now the fully working code looks like this:

void mergeSort(vector<int> &mass){
	if(mass.size() <= 16)
		sort(mass.begin(),mass.end());
	else {
		vector<int> u,v;
		int size1,size2;
		size1 = div(mass.size(),2).quot;
		size2 = div(mass.size()+1,2).quot;
		u.resize(size1);
		v.resize(size2);
		
		u.assign(mass.begin(),mass.end()-size1);
		v.assign(mass.begin()+size1+1,mass.end());

		mergeSort(u);
		mergeSort(v);
		mass.clear();
		mass.resize(u.size()+v.size());
		merge(u.begin(),u.end(),v.begin(),v.end(),mass.begin());
	}
};