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;
               
                }
        }
}

---

Start by using the at member function instead of the subscript operator. You'll have an easier time of finding the problem that way.

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

>we have to use vectors with the subscripts
Well, since the subscript operator is typically unchecked, you're making your debugging job harder by using it. Who says you can't add debugging code and then change it back when you find the problem? How to use at? Change v[i] to v.at ( 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::out_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