template <class T>
void bag<T>::merge(int p, int q, int r)
{
	int length1=q-p+1;
	int length2=r-q;
	int size1=length1;
	int size2=length2;
	T A1[length1], A2[length2];
	T sort[length1+length2];
	
	int i=0;
	int j;
	
	for(j=0; j<length1; j++)
		A1[j]=array[p+j];
		
	for(j=0;j<length2; j++)
		A2[j]=array[p+j+length1];
	
	do
	{
		if (A1[0]<=A2[0])
		{
			sort[i]=A1[0];
			size1--;
			i++;
			if(size1!=0)
			{
				for(j=0; j<size1; j++)
					A1[j]=A1[j+1];
			}
		}
		
		else
		{
			sort[i]=A2[0];
			size2--;
			i++;
			if(size2 !=0)
			{
				for(j=0; j<size2; j++)
					A2[j]=A2[j+1];
			}
		}
	}while(size1 !=0 && size2 !=0);
	
	j=0;
	if (size1==0)
	{
		while(i<length1+length2)
		{
			sort[i]=A2[j];
			j++;
			i++;
		}
	}

	else
	{
		while(i<length1+length2)
		{
			sort[i]=A1[j];
			j++;
			i++;
		}
	}

	i=0;
	for(j=p; j<=r; j++)
	{
		array[j]=sort[i];
		i++;
	}
}