/*
  Name:              InsertionSort.cpp
  Copyright:         taolizao
  Author:            zhangjian
  Date: 19-10-08 17:27
  Description: 
*/
#include "InsertionSort.h"

template<class T>
int InsertionSort(T a[],T Link[],int left,int right)
{
	T * temp=new T[right-left+1];
	int * rank=new int[right-left+1];
	int i,j,k,start;
	for(i=0;i<right-left+1;i++)
	{
	   temp[i]=a[i+left];
		 rank[i]=i+left;
  }	
	
	for(i=0;i<right-left;i++)
	{
		T t=temp[i+1];
		for(j=i;j>=0&&t<temp[j];j--)
		{					  
		   temp[j+1]=temp[j];
		   rank[j+1]=rank[j];
	  }
	  temp[j+1]=t;
	  rank[j+1]=i+left+1;	
	}
	
	start=rank[0];
	k=rank[0];
	
	for(i=1;i<right-left+1;i++)
	{		
	  Link[k]=rank[i];
	  k=rank[i];
  }                  
	Link[k]=-1;
		  
/*	cout<<start<<endl;
	for(i=0;i<right-left+1;i++)
	{
		cout<<Link[i+left]<<" ";
	}
	cout<<endl; */		
	return start;
}