//sort the A[p..q] in an ascend order
//tmp is needed
void merge(int *A,int *tmp,int p,int r,int q)
{
	//create the left and right array from A
	//left A[p..r],right A[r+1..q] 
	int *L=&A[p];
	int *R=&A[r+1];
	int i=0,j=0,t=0;
	//merge the left and right into tmp
	while(i<=(r-p)&&j<=(q-r-1))
	{
		if(L[i]<=R[j])
		tmp[t++]=L[i++];
		else
		tmp[t++]=R[j++];
	}
	//copy the rest of L or R into tmp
	while(i<=(r-p)) tmp[t++]=L[i++];
	while(j<=(q-r-1)) tmp[t++]=R[j++];
	//return the tmp back into A
	for(int i=0;i<t;i++)
	A[i+p]=tmp[i];
	return;
}
void mergeSort(int *A,int *tmp,int p,int q)
{
	if(p>=q) return;
	int r=(p+q)/2;
	//sort the two part recursively
	mergeSort(A,tmp,p,r);
	mergeSort(A,tmp,r+1,q);
	merge(A,tmp,p,r,q);
	return;
}