//優化的兩路歸并排序類

#include "ImprovedInsertSorter.h"
#define THRESHOLD 16

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

template <class Record,class Compare>
ImprovedTwoWayMergeSorter<Record,Compare>::ImprovedTwoWayMergeSorter()
{
	TempArray = new Record[1000000];
}

template <class Record,class Compare>
ImprovedTwoWayMergeSorter<Record,Compare>::~ImprovedTwoWayMergeSorter()
{
	delete[] TempArray;
}

//優化的兩路歸并排序，Array[]為待排序數組，left，right分別為數組兩端
template <class Record,class Compare>
void ImprovedTwoWayMergeSorter<Record,Compare>::Sort(Record Array[], int left, int right) 
{ 
	if (right <= left)					// 如果只含有一個元素，直接返回
		return;    
	if (right-left+1 <= THRESHOLD)
	{
		ImprovedInsertSorter<Record,Compare> insert_sorter;
		insert_sorter.Sort(&Array[left],right-left+1);
	}
	else
	{
		int middle=(left+right)/2;		//從中間劃分為兩個子序列
		Sort(Array,left,middle);		//對左邊一半進行遞歸
		Sort(Array,middle+1,right);		//對右邊一半進行遞歸
		Merge(Array,left,right,middle);	// 進行歸并
	}

}

//歸并過程
template <class Record,class Compare>
void ImprovedTwoWayMergeSorter<Record,Compare>::Merge(Record Array[],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--];
}