//二分法插入排序類
#include "InsertSorter.h"

template <class Record,class Compare>
class BinaryInsertSorter:public InsertSorter<Record,Compare>
{
public:
	void Sort(Record Array[],int n);
};

//二分法插入排序，Array[]為待排序數組，n為數組長度
template <class Record,class Compare>
void BinaryInsertSorter<Record,Compare>::Sort(Record Array[], int n) 
{ 
	Record TempRecord;		//用來保存當前待插入紀錄的臨時變量
	int left,right,middle;  //記錄已排好序序列的左、右、中位置
	for (int i=1;i<n;i++)  //插入第i個記錄
	{          
		TempRecord = Array[i];	//將當前待插入記錄保存在臨時變量中
		left = 0; right = i-1;	//記錄已排好序序列的左右位置
		while(left <= right)	//開始查找待插入記錄的正確位置
		{
			middle = (left+right)/2;		//記錄中間位置
			//如果待插入記錄比中間記錄小，就在左一半中查找，否則，在右一半中查找
			if (Compare::lt(TempRecord, Array[middle]))
				right = middle-1;
			else left = middle+1;
		}
		//將前面所有大于當前待插入記錄的記錄后移
		for(int j = i-1; j >= left; j --)
			Array[j+1] = Array[j];
			Array[left] = TempRecord;	//將待插入記錄回填到正確位置
	}
}