//兩路歸并排序類
#include "Sorter.h"

template <class Record,class Compare>
class TwoWayMergeSorter:public Sorter<Record,Compare>
{	//兩路歸并排序類
private:
	void Merge(Record Array[],Record TempArray[],int left,int right,int middle);//歸并過程
public:
	void Sort(Record Array[],Record TempArray[],int left, int right);
};

//兩路歸并排序，Array[]為待排序數組，n為數組長度
template <class Record,class Compare>
void TwoWayMergeSorter<Record,Compare>::Sort(Record Array[],Record TempArray[], int left, int right) 
{ 
	if (left < right)					// 如果只含有一個元素，直接返回
	{
		int middle=(left+right)/2;		//從中間劃分為兩個子序列
		Sort(Array,TempArray,left,middle);		//對左邊一半進行遞歸
		Sort(Array,TempArray,middle+1,right);		//對右邊一半進行遞歸
		Merge(Array,TempArray,left,right,middle);	// 進行歸并
	}

}

//歸并過程
template <class Record,class Compare>
void TwoWayMergeSorter<Record,Compare>::Merge(Record Array[],Record TempArray[],int left,int right,int middle)
{
	for (int j=left; j<=right; j++)   			// 將數組暫存入臨時數組
		TempArray[j] = Array[j];
	int index1=left;		//左邊子序列的起始位置
	int index2=middle+1;	//右邊子序列的起始位置
	int i=left;				//從左開始歸并
	while ((index1 <= middle)&&(index2 <= right))
	{
		//取較小者插入合并數組中
		if (Compare::lt(TempArray[index1], TempArray[index2]))
			Array[i++] = TempArray[index1++];
		else
			Array[i++] = TempArray[index2++];
	}
	while (index1 <= middle)
		Array[i++] = TempArray[index1++];
	while (index2 <= right)
		Array[i++] = TempArray[index2++];
}