归并排序（Merge Sort）

归并排序是建立在【归并】操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，它是稳定的排序算法，其时间复杂度为 \(nlogn\)。

归并操作可以将两个有序的序列合并为一个有序序列，也就是说，归并排序的基本思想就是不听的去合并两个有序序列。关键是我们如何去将无序序列构造成两个有序序列呢？

我们想到，如果一个序列只有一个元素的话，那么其就是有序的。所以，归并排序就是通过不停的将序列拆分直至只有 1 个元素，然后再合并，最终使得整个序列变得有序。

注意：这个拆分的过程就是递归的过程，递归到最后，就变成：

1. 两个包含 1 个元素的序列合并成一个包含 2 个元素的有序序列；
2. 两个包含 2 个元素的有序序列合并成一个包含 4 个元素的有序序列；
3. … 依次类推，直至整个序列变得有序。

算法实现时，要额外去实现下合并两个有序序列的操作函数 merge，当然也可以直接使用 STL 中的 merge 算法。下面为归并排序的实现代码：

#include <iostream>
using namespace std;


//合并两个有序序列
void merge(int arr[], int start, int mid, int end, int* tempSpace)
{
	int iStart = start;
	int iEnd = mid;

	int jStart = mid + 1;
	int jEnd = end;

	int length = 0;

	while (iStart <= iEnd && jStart <= jEnd)
	{

		if (arr[iStart] < arr[jStart])
		{
			tempSpace[length] = arr[iStart];
			iStart++;
			length++;
		}
		else
		{
			tempSpace[length] = arr[jStart];
			jStart++;
			length++;
		}

	}

	while (iStart <= iEnd)
	{
		tempSpace[length] = arr[iStart];
		length++;
		iStart++;
	}

	while (jStart <= jEnd)
	{
		tempSpace[length] = arr[jStart];
		length++;
		jStart++;
	}

	//将辅助空间中数据覆盖到原来空间
	for (int i = 0; i < length; ++i)
	{
		arr[start + i] = tempSpace[i];
	}

}


// 升序
void merge_sort(int arr[], int start, int end, int* tempSpace)
{
	if (start == end)
	{
		return;
	}

	//确定中间元素
	int mid = (start + end) / 2;
	//拆分左半部分
	merge_sort(arr, start, mid, tempSpace);
	//拆分右半部分
	merge_sort(arr, mid + 1, end, tempSpace);
	//合并两个有序序列
	merge(arr, start, mid, end, tempSpace);
}

int main()
{
	int arr[] = { 6, 8, 5, 7, 4 };
	int len = sizeof(arr) / sizeof(int);
	// 开辟辅助空间，空间大小等于数组大小
	int* tempSpace = new int[len];

	merge_sort(arr, 0, len - 1, tempSpace);

	delete[] tempSpace;

	for (auto v : arr) cout << v << " ";
	cout << endl;

	return 0;
}

程序执行结果：

4 5 6 7 8