//優化的兩路歸并排序類
#include "ImprovedInsertSorter.h"
#define THRESHOLD 16

template <class Record,class Compare>
class ImprovedTwoWayMergeSorter:public Sorter<Record,Compare>
{
private:
	void Merge(Record Array[],Record TempArray[],int left,int right,int middle);	//歸并過程
	void DoSort(Record Array[],Record TempArray[],int left, int right);
public:
	void Sort(Record Array[],Record TempArray[],int left, int right);

};


//優化的兩路歸并排序，Array[]為待排序數組，left，right分別為數組兩端
template <class Record,class Compare>
void ImprovedTwoWayMergeSorter<Record,Compare>::Sort(Record Array[],Record TempArray[], int left, int right) 
{
	DoSort(Array,TempArray,left,right);
	ImprovedInsertSorter<Record,Compare> insert_sorter;
	insert_sorter.Sort(&Array[left],right-left+1);
}

template <class Record,class Compare>
void ImprovedTwoWayMergeSorter<Record,Compare>::DoSort(Record Array[],Record TempArray[],int left, int right)
{ 
	if (right <= left)				// 如果只含有一個元素，直接返回
		return;    
	//如果序列長度小于等于閾值(16最佳)，采用直接插入排序
	if (right-left+1 > THRESHOLD)
	{
		int middle=(left+right)/2;		//從中間劃分為兩個子序列
		DoSort(Array, TempArray ,left,middle);		//對左邊一半進行遞歸
		DoSort(Array, TempArray ,middle+1,right);		//對右邊一半進行遞歸
		Merge(Array, TempArray ,left,right,middle);		// 進行歸并
	}
}

//歸并過程
template <class Record,class Compare>
void ImprovedTwoWayMergeSorter<Record,Compare>::Merge(Record Array[],Record TempArray[],int left,int right,int middle)
{
	int index1,index2;				//兩個子序列的起始位置
	int i,j,k ;
	for (i=left; i<=middle; i++)	//復制左邊的子序列
		TempArray[i] = Array[i];
	for (j=1; j<=right-middle; j++)	//復制右邊的子序列，但順序顛倒過來
		TempArray[right-j+1] = Array[j+middle];
	// 開始歸并
	for (index1=left,index2=right,k=left; k<=right; k++)
		if (Compare::lt(TempArray[index1], TempArray[index2]))
			Array[k] = TempArray[index1++];
		else Array[k] = TempArray[index2--];
}