#include "MergeSortL.h"
#include "InsertionSort.h"

template<class T>
int MergeSortL(T a[],T Link[],int left,int right)
{
	int q,r;
	if(right-left+1<16)
	  InsertionSort(a,Link,left,right);
	else
	{
		int mid=(left+right)/2;
		q=MergeSortL(a,Link,left,mid);
		r=MergeSortL(a,Link,mid+1,right);
//		cout<<"q="<<q<<endl<<"r="<<r<<endl;
		MergeL(a,Link,q,r,right-left+1);  
	}
}

template<class T>
int MergeL(T a[],T Link[],int q,int r,int len)
{
	 T * temp=new T[len+1];
	 int i,j,k;
	 int start;
	 i=q;
	 j=r;
	 k=0; 
	 if(i!=-1&&j!=-1)
	 {
	   if(a[i]<=a[j])
	      start=i;
	   else 
	      start=j;
	}                              
	 while(i!=-1&&j!=-1)
	 {
			if(a[i]<=a[j])
			{
				temp[k]=i;
				k=i;
				i=Link[i];
			}
			else
			{
				temp[k]=j;
				k=j;
				j=Link[j];
			}
				
	}
	if(i==-1)
	{
		while(j!=-1)
		{
			temp[k]=j;
			k=j;
			j=Link[j];
		}
		temp[k]=-1;
	}
	if(j==-1)
	{
		while(i!=-1)
		{
			temp[k]=i;
			k=i;
			i=Link[i];
		}
		temp[k]=-1;
	}

/*	cout<<"temp[]=";
	for(i=0;i<11;i++)
	{
	   cout<<temp[i]<<" ";
		}
	cout<<endl<<"Link[]=";
		
	cout<<Link[0]<<" ";  */
	for(i=0;i<len;i++)
	{
	   Link[i]=temp[i];
//	   cout<<Link[i]<<" ";
		}

	cout<<endl; 
  return start;
}