归并排序

• 将待排序的线性表不断地切分成若干个子表，直到每个子表只包含一个元素，这时，可以认为只包含一个元素的子表是有序表。
• 将子表两两合并，每合并一次，就会产生一个新的且更长的有序表，重复这一步骤，直到最后只剩下一个子表，这个子表就是排好序的线性表。
• O(nlogn)

#include<iostream>
#include<cstdlib>
#define ElemType_I int

using namespace std;

void Merge(ElemType_I A[], ElemType_I left, ElemType_I mid, ElemType_I right)             //合并
{
	ElemType_I *B = new ElemType_I[right - left + 1];                                     //申请辅助数组
	ElemType_I i = left;
	ElemType_I j = mid + 1;
	ElemType_I k = 0;

	while (i <= mid && j <= right)
		if (A[i] <= A[j])
			B[k++] = A[i++];
		else
			B[k++] = A[j++];

	while (i <= mid)
		B[k++] = A[i++];

	while (j <= right)
		B[k++] = A[j++];

	for (i = left, k = 0; i <= right; i++)
		A[i] = B[k++];

	delete[] B;
}

void MergeSort(ElemType_I A[], ElemType_I left, ElemType_I right)                             //递归形式的归并排序
{
	if (left < right)
	{
		ElemType_I mid;
		mid = (left + right) / 2;
		MergeSort(A, left, mid);
		MergeSort(A, mid + 1, right);
		Merge(A, left, mid, right);
	}
}

int main()
{
	ElemType_I n;
	cin >> n;
	ElemType_I *A = new ElemType_I[n];
	for (int i = 0; i < n; i++)
		cin >> A[i];

	MergeSort(A, 0, n - 1);                                          //调用归并排序              

	for (int i = 0; i < n; i++)
		cout << A[i] << " ";

	cout << endl;
	//system("pause");                                                        //输出暂停，头文件<cstdlib>

	return 0;
}