排序算法：歸并算法

歸并算法理解起來還是比較簡單的，基本原理是將兩個(gè)已排序的數(shù)列歸并成一個(gè)排序的數(shù)列。那么要將一個(gè)無序的數(shù)列利用歸并算法排序，首先生成短的有序序列，利用歸并算法，逐漸合成長的有序序列。最直接的歸并方法為：對(duì)于兩個(gè)有序序列p1, p2，從p2中逐個(gè)選擇元素插入到p1中，這種方法簡單，但是效率不高，如果采用二分法查找并且分段插入，將能提高歸并效率。

分段歸并算法的原理是：對(duì)于有序序列p1和p2，建立三元結(jié)構(gòu)（b, e, p），b為begin，代表p2序列中要插入到p1中的片段頭標(biāo)識(shí); e為end，代表p2序列要插入到p1中的片段的尾標(biāo)識(shí)，p為point，代表p2要插入到p1中的位置。遍歷p2序列，找到所有的三元結(jié)構(gòu)，然后利用三元結(jié)構(gòu)將p2序列歸并到p1序列。

可以通過一個(gè)例子來說明如何使用三元結(jié)構(gòu)：

有序序列：p1: 10, 18, 30, 41; p2: 3, 6, 12, 52

從p2序列第一個(gè)元素開始：p1: 10, 18, 30, 41; p2: 3, 6, 12, 52 —— (0, e, p)，begin = 0

可以看到p2第一個(gè)元素的插入點(diǎn)為0：p1: 10, 18, 30, 41; p2:?3, 6, 12, 52 —— (0, e, 0)，point = 0, 因?yàn)閜2(0) = 3小于p1(0) = 10

然后通過快速查找算法搜索10在p2中的位置：p1:?10, 18, 30, 41; p2:?3, 6, 12, 52 —— (0, 2, 0)，end = 2，這樣就找到了一個(gè)三元體；

類似的有：p1:?10, 18, 30, 41; p2:?3,?6,?12, 52 —— (2, 3, 1)

? ? ? ? ? ? ? ? ? ? p1:?10,?18, 30, 41; p2:?3,?6,?12,?52?—— (3, 4, 4)

利用生成的所有三元體結(jié)構(gòu)，將p2數(shù)據(jù)插入到p1中得到：3, 6, 10, 12, 18, 30, 41, 52

#include 
#include 

#define LOG2(x) ((log(x)/log(2)))

using namespace std;

template
void MergeSort(vector &vec);

int main()
{
	int att[] = { 10, 4, 23, 46, 20, 5, 3, 88, 8, 44, 53, 25, 86, 32, 16, 11};
	vector vec(&att[0], &att[sizeof(att)/sizeof(int)]);
	
	MergeSort(vec);

	return 0;
}


template
void MergeSort(vector &vec)
{
	int VSize = vec.size();
	if (VSize <= 1)
		return;

	double Kf = LOG2(VSize);
	int K = ((int)floor(Kf) == (int)ceil(Kf)) ? (int)floor(Kf) : (int)ceil(Kf);
	T maxV = vec[0];
	for (int vIdx = 0; vIdx < VSize; vIdx++)
	{
		if ((0 == (vIdx % 2)) && (vIdx + 1 < VSize) && (vec[vIdx] > vec[vIdx + 1]))
		{
			vec[vIdx] ^= vec[vIdx + 1];
			vec[vIdx + 1] ^= vec[vIdx];
			vec[vIdx] ^= vec[vIdx + 1];
		}

		maxV = (maxV > vec[vIdx]) ? maxV : vec[vIdx];
	}

	// insert max value at the end of vector to make up of vector length to pow(2, K)
	if ((int)pow(2, K) > VSize)
		vec.insert(vec.end(), pow(2, K) - VSize, maxV);
	int newVSize = vec.size();

	int Km = 2;

	typedef struct
	{
		int begin;
		int end;
		int point;
	} TripleStruct;

	for (int kIdx = 2; kIdx <= K; kIdx++)
	{
		for (int kmIdx = 0; kmIdx < newVSize/(Km*2); kmIdx++)
		{
			vector vecTMP1(&vec[kmIdx * Km * 2], &vec[kmIdx * Km * 2 + Km]);
			vector vecTMP2(vec.begin() + kmIdx * Km * 2 + Km, vec.begin() + kmIdx * Km * 2 + Km * 2);
			vector tripleList;

			if (vecTMP2[0] > vecTMP1[Km - 1])
				continue;

			for (int pIdx = 0; pIdx < Km; pIdx++)
			{
				int left = pIdx;
				int right = Km - 1;

				if (vecTMP2[Km - 1] < vecTMP1[0])  // vecTMP2 the whole element locates at the front of vecTMP1
				{
					TripleStruct triple = { 0, Km, 0 };
					tripleList.push_back(triple);
					break;
				}

				if (vecTMP2[pIdx] > vecTMP1[Km - 1])
				{
					TripleStruct triple = { pIdx, Km, Km };
					tripleList.push_back(triple);
					break;
				}

				// get insert point
				TripleStruct triple;
				triple.begin = pIdx;
				if (vecTMP2[pIdx] < vecTMP1[left])
					triple.point = left;
				else
				{
					while (left != right)
					{
						int avg = (left + right) / 2;
						if (vecTMP2[pIdx] > vecTMP1[avg])
							left = avg;
						else
							right = avg;

						if (left + 1 == right)
							left = right;
					}
					triple.point = left;
				}

				// get insert end
				int l_left = pIdx + 1;
				int l_right = Km - 1;
				if (pIdx == Km - 1)
				{
					triple.end = Km;
				}
				else if (vecTMP1[left] < vecTMP2[l_left])
					triple.end = l_left;
				else
				{
					while (l_left != l_right)
					{
						int avg = (l_left + l_right) / 2;
						if (vecTMP1[left] < vecTMP2[avg])
							l_right = avg;
						else
							l_left = avg;

						if (l_left + 1 == l_right)
							l_left = l_right;
					}
					triple.end = l_left;
				}
				pIdx = l_left - 1;

				tripleList.push_back(triple);

			}

			// Process Inserting
			int insertLength = 0;
			int tripleSize = tripleList.size();
			for (int tIdx = 0; tIdx < tripleSize; tIdx++)
			{
				vecTMP1.insert(vecTMP1.begin() + insertLength + tripleList[tIdx].point, vecTMP2.begin() + tripleList[tIdx].begin, vecTMP2.begin() + tripleList[tIdx].end);
				insertLength += tripleList[tIdx].end - tripleList[tIdx].begin;
			}

			memcpy((char*)&vec[kmIdx * Km * 2], (char*)&vecTMP1[0], sizeof(T)*vecTMP1.size());
		}
		Km *= 2;
	}

	if ((int)pow(2, K) > VSize)
	{
		vector tmpvec(&vec[0], &vec[VSize]);
		vec.assign(tmpvec.begin(), tmpvec.end());
	}

	for (int vIdx = 0; vIdx < VSize; vIdx++)
	{
		cout << "indx " << vIdx << " value " << vec[vIdx] << endl;
	}


	return;
}