void merge(int low,int mid,int high)
{	int size, p, q, i, r;
	size = high - low + 1; //size of array c
	int c[size]; //array c - the temporary array for sorting
	p=low; //index for a[i]...a[mid]
	q=mid+1; //index for a[mid + 1]...a[j]
	while((p<=mid)&&(q<=high))
	{		if(a[p]<=a[q]) //copy smaller value to local array c
		{		c[i]=a[p];
				p++;
		  }
		else
		  {		c[i]=a[q];
				q++;
		  }
	  i++;
	}
	while (a[p]<= mid)//copy the rest of the longer array
	{	 c[i] = a[p];
	}
	while (a[q]<=high)//copy the rest of the larger array
	 {	 c[i]=a[q];
	 }
	for (i=low; i<=high; i++)//copy back from temp array to main array
		{	 a[i]=c[i];
		 }}
void merge(int low,int mid,int high)
{	int size, p, q, i, r;
	size = high - low + 1; //size of array c
	int c[size]; //array c - the temporary array for sorting
	p=low; //index for a[i]...a[mid]
	q=mid+1; //index for a[mid + 1]...a[j]
	while((p<=mid)&&(q<=high))
	{		if(a[p]<=a[q]) //copy smaller value to local array c
		{		c[i]=a[p];
				p++;
		  }
		else
		  {		c[i]=a[q];
				q++;
		  }
	  i++;
	}
	while (a[p]<= mid)//copy the rest of the longer array
	{	 c[i] = a[p];
	}
	while (a[q]<=high)//copy the rest of the larger array
	 {	 c[i]=a[q];
	 }
	for (i=low; i<=high; i++)//copy back from temp array to main array
		{	 a[i]=c[i];
		 }}
int main()
{ 	long timeElapsed;
	timeElapsed = clock();
	int num,i,elem, percent;
	//a[num];
	cout<<"*********************************************************************"<<endl;
	cout<<"                             MERGE SORT PROGRAM"<<endl;
	cout<<"**********************************************************************"<<endl<<endl<<endl;
	cout<<"Please Enter THE NUMBER OF ELEMENTS you want to sort[THEN PRESS ENTER]:"<<endl;
	cin>>num;
	cout<<"Please Enter THE PERCENTAGE you want to sort[THEN PRESS ENTER]:"<<endl;
	cin>>percent;
	//for (i=1; i<=num; i++)
	for (i=0; i<num; i++)
	{	elem =(rand()+1);
        cout<<endl<<"element "<<i<<"is "<<elem<<endl;
        a[i]= elem;
        cout<<"When i is "<<i<<" ai is "<<a[i];
    }
    merge_sort(0,num);
    cout<<endl<<"So, the sorted list (using MERGE SORT) will be : "<<endl;
    for(i=0;i<num;i++)
    {  cout<<a[i]<<" ";
    }
    cout<<endl<<endl<<"Time Elapsed is: "<<timeElapsed<<endl<<endl<<endl<<endl;
    system("PAUSE");