Vector subscript out of range (merge sort)

[afranco527]

Hi all,

I am trying to make the merge sort algorithm using vectors. Everything compiles fine but when I run the program, I get the "vector subscript out of range error."

I can pinpoint the error is coming from line 58 because when I comment the for loop out, the program runs fine but with no results obviously.

Can someone help me spot where I am going wrong?

Thanks

#include <iostream>
#include <ctime>
#include <cstdlib>
#include <vector>
using namespace std;

void merge(int A[],int lower,int middle,int higher);
void mergeSort(int A[],int lower,int higher);


int main()
{
	srand(time(0));

	int list[10];

	for(int i=0;i<10;i++)
		list[i]=rand()%100+1;

	for(int i=0;i<10;i++)
		cout<<list[i]<<" ";

	cout<<endl<<endl;

	mergeSort(list,0,9);

	for(int i=0;i<10;i++)
		cout<<list[i]<<" ";

	cout<<endl;

	system("PAUSE");
}

void merge(int A[],int lower,int middle,int higher)
{
	int n1=(middle-lower)+1;
	int n2=higher-middle;

	vector<int> L(n1+1);
	vector<int> R(n2+1);

	
	for(int i=1;i<n1;i++)
	{
		L[i]=A[(lower+i)-1];
	}
	for(int j=1;j<n2;j++)
	{
		R[j]=A[middle+j];
	}

	L[n1+1]=0;
	R[n2+1]=0;
	int i=1,j=1;
	for(int k=lower;k<higher;k++)
	{
		if(L[i]<=R[j])
		{
			A[k]=L[i];
			i++;
		}
		else
		{
			A[k]=R[j];
			j++;
		}
	}
}

void mergeSort(int A[],int lower, int higher)
{
	int middle;

	if(lower<higher)
	{
		middle=((lower+higher)/2);
		mergeSort(A,lower,middle);
		mergeSort(A,middle+1,higher);
		merge(A,lower,middle,higher);
	}


}

[MiiNiPaa]

L[n1+1]=0;
R[n2+1]=0;

There are no such elements in either vector. Maximum allowed index is

L[n1]
R[n2]

Additionally int i=1,j=1; is wrong too. Array (and vector) indices starts with 0.

[afranco527]

Yes you're right about the first part. I forgot to remove those lines. My professor gave us the psuedocode and we had to try and write the real code and following it.

http://imgur.com/G4DFXDk

That is what I was following. Did I do something incorrect?

[shadowCODE]

In real life counting starts from 1. In computers, it starts from 0.

speaking to a human, (1 to n) is more appropriate and understandable than (0 to n-1).

Consider this example.

string months[] = {"Jan","Feb","March"...};
int choice;
cout<<"Enter the number of the month to know the name: ";
cin>>choice;

Wouldn't you(human) enter 2 as choice if you wanted February?
Ill then print months[choice - 1.

http://www.quora.com/Why-does-Introduction-to-Algorithms-by-CLRS-index-arrays-start-with-1-and-not-0