歸并排序

歸并算法：

對于資料較大的輸入，歸并排序是比較快的一個算法。該算法采用的是分治法的思想。

歸并排序的原理：先将資料分開排序，然後再合并起來，最後形成一個排好的序列。

void _Merge(int* a, int* tmp, int begin1, int end1, int begin2, int end2)//7-2區間合并
{
	int index = 0;
	while (begin1<=end1&&begin2<=end2)
	{
		if (a[begin1] < a[begin2])
		{
			tmp[index++] = a[begin1++];
		}
		else
		{
			tmp[index++] = a[begin2++];
		}
	}
	while (begin1 <= end1)
	{
		tmp[index++] = a[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[index++] = a[begin2++];
	}

}

void _MergeSort(int* a, int* tmp, int begin, int end)//7-1畫區間
{
	if (begin >= end)
	{
		return;
	}
	int mid = begin + ((end - begin) >> 1);
	_MergeSort(a, tmp, begin, mid);
	_MergeSort(a, tmp, mid + 1, end);
	_Merge(a, tmp, begin, mid, mid + 1, end);
	memcpy(a + begin, tmp, sizeof(int)*(end - begin + 1));
}
void MergeSort(int* a, size_t n)// 7歸并排序
{
	assert(a);
	int* tmp = new int[n];
	_MergeSort(a, tmp, 0, n - 1);
	delete[] tmp;
}
           

歸并排序時間複雜度是：O(N* LogN)，                   空間複雜度是：O(N).

歸并排序比較占記憶體，但是高校且穩定的一種排序。