Thread: My Merge Sort is not working???? WHY?

here is the code. I get a segmentation fault every time run.

Code:

//Mergesort
void mergesort(vector<string>& word_vector, int start, int stop) 
{
   int mid;  
   if (start < stop)
   {
   	mid=(start+stop/2);
   	mergesort(word_vector, start, mid);
   	mergesort(word_vector, mid+1, stop);
   	merge(word_vector, start, mid, stop);
   }
}

void merge(vector<string>& word_vector, int start,int mid, int stop)
{
	int i,j,k,na,nb;
	cout << start<< "  " << mid << "  "<< stop << endl;
	vector<string> vector_L;
	vector<string> vector_R;

	
	na = mid-start +1;
	nb = stop - mid;
		
	for (i = 1; i <= na; i++)
	{ 
		vector_L.push_back(word_vector[start+i-1]);
	}
	for (i = 1; i <= nb; i++)
	{
		vector_R.push_back(word_vector[mid+1]);
	}
	
	i = 1;
	j= 1;
	cout <<"Left Size is " << vector_L.size() << "   Right Size is " << vector_R.size() << endl;
	for (k=start; k <= stop; k++)
	{	cout <<"i is "<< i << "   j is  " << j <<"   k is  " << k << endl;
		if (strcmp(vector_L[i].c_str(),vector_R[j].c_str()) < 0)
		{
			word_vector[k] = vector_L[i];
			i = i + 1;
		} 
		else
		{
			word_vector[k] = vector_R[j];
			j = j + 1;
		
		}
	}
}

This is for a college class ... only problem left in my program...we have to use vectors with the subscripts

For debugging purposes, change it to at() and then change it back when you find out where you are accessing the vector incorrectly (or when you find out that you are not).

Also check that the vector passed in has the right size, and that you are only accessing elements from 0 to size()-1.

I have never used the at() how would I

Ok I will, but what will this do??

The error I get is
DOING MERGE SORT
Start 0 Stop 13
Start 0 Stop 6
Start 0 Stop 3
Start 0 Stop 1
Start 0 Stop 0
Start 1 Stop 1


call to merge

0 0 1
Left Size is 1 Right Size is 1
i is 1 j is 1 k is 0
terminate called after throwing an instance of 'std:ut_of_range'
what(): vector::_M_range_check
Aborted


the new code is:

Code:

//Mergesort
void mergesort(vector<string>& word_vector, int start, int stop) 
{
   int mid;  
   cout << "Start " << start << "  Stop " << stop << endl; 
   if (start < stop)
   {
   	mid=(start+stop/2);
   	mergesort(word_vector, start, mid);
   	mergesort(word_vector, mid+1, stop);
   	merge(word_vector, start, mid, stop);
   }
  
}

void merge(vector<string>& word_vector, int start,int mid, int stop)
{	
	cout <<endl<<endl << "call to merge"<< endl << endl;
	int i,j,k,na,nb;
	cout << start<< "  " << mid << "  "<< stop << endl;
	vector<string> vector_L;
	vector<string> vector_R;

	
	na = mid-start+1;
	nb = stop - mid;
		
	for (i = 1; i <= na; i++)
	{ 
		vector_L.push_back(word_vector.at(start+i-1));
	}
	for (i = 1; i <= nb; i++)
	{
		vector_R.push_back(word_vector.at(mid+1));
	}
	
	
	i = 1;
	j= 1;
	cout <<"Left Size is " << vector_L.size() << "   Right Size is " << vector_R.size() << endl;
	for (k=start; k <= stop; k++)
	{	cout <<"i is "<< i << "   j is  " << j <<"   k is  " << k << endl;
		if (strcmp(vector_L.at(i).c_str(),vector_R.at(j).c_str()) < 0)
		{
			word_vector.at(k) = vector_L.at(i);
			i = i + 1;
		} 
		else
		{
			word_vector.at(k) = vector_R.at(j);
			j = j + 1;
		
		}
	}
	
	

}

I have now fixed the problem with the sementation fault but I am getting in an infinate loop in the small merge function. The code is as follows:

Code:

//Mergesort
void mergesort(vector<string>& word_vector, int start, int stop) 
{
   int mid;  
   cout << "Start " << start << "  Stop " << stop << endl; 
   if (start < stop)
   {
   	mid=(start+stop/2);
   	mergesort(word_vector, start, mid);
   	mergesort(word_vector, mid+1, stop);
   	merge(word_vector, start, mid, stop);
   }
  
}

void merge(vector<string>& word_vector, int start,int mid, int stop)
{	
	cout <<endl<<endl << "call to merge"<< endl << endl;
	int i,j,k,na,nb;
	cout << start<< "  " << mid << "  "<< stop << endl;
	vector<string> vector_L;
	vector<string> vector_R;

	
	na = mid-start+1;
	nb = stop - mid;
		
	cout << "na: " << na << "    nb: " << nb << endl;
	
	for (i = 1; i <= na; i++)
	{ 
		vector_L.push_back(word_vector.at(start+i-1));
	}
	for (i = 1; i <= nb; i++)
	{
		vector_R.push_back(word_vector.at(mid+1));
	}
	
	i = 0;
	j= 0;
	
	cout <<"Left Size is " << vector_L.size() << "   Right Size is " << vector_R.size() << endl;
	cout << "Start " << start << "  Stop "<< stop << endl;
	for (k=start; k < stop; k++)
	{	cout <<"i is "<< i << "   j is  " << j <<"   k is  " << k << endl;
		if (strcmp(vector_L.at(i).c_str(),vector_R.at(j).c_str()) < 0)
		{
			cout << endl << endl << "Trying first if" << endl;
			word_vector.at(k) = vector_L.at(i);
			i = i + 1;
		} 
		else
		{
			cout << endl << endl << "Trying second if" << endl;
			word_vector.at(k) = vector_R.at(j);
			j = j + 1;
		
		}
	}
	
}

The numbers it is getting stuck on are
start = 2 stop = 3