常见排序算法--合并排序

思路:将一个无序的序列分组，直至分为每两个元素一组（如果有单个元素剩余，则可以剩余的单个元素自己一组），小组内排序，然后合并成一个有序的序列。

例子： 排序过程如图所示：图片摘选自：https://blog.csdn.net/ZY_cat/article/details/78404257

程序实现：

#include <iostream>  
using namespace std;
void merge(int *data, int p, int q, int r)
{
	int n1, n2, i, j, k;
	n1 = q - p + 1;
	n2 = r - q;
	int *left = new int[n1];
	int *right = new int[n2];
	for (i = 0; i<n1; i++)  //对左数组赋值  
		left[i] = data[p + i];
	for (j = 0; j<n2; j++)  //对右数组赋值  
		right[j] = data[q + 1 + j];
	i = j = 0;
	k = p;
	while (i<n1 && j<n2) //将数组元素值两两比较，并合并到data数组  
	{
		if (left[i] <= right[j])
			data[k++] = left[i++];
		else
			data[k++] = right[j++];
	}
	for (i; i<n1; i++) //如果左数组有元素剩余，则将剩余元素合并到data数组  
		data[k++] = left[i];
	for (j; j<n2; j++) //如果右数组有元素剩余，则将剩余元素合并到data数组  
		data[k++] = right[j];
}

void mergeSort(int *data, int p, int r)
{
	int q;
	if (p < r) //只有一个或无记录时不须排序   
	{
		q = (int)((p + r) / 2);      //将data数组分成两半     
		mergeSort(data, p, q);   //递归拆分左数组  
		mergeSort(data, q + 1, r); //递归拆分右数组  
		merge(data, p, q, r);    //合并数组  
	}
}
int main()
{
	int n;
	cout << "请输入数组的长度: ";
    cin >> n;	
	int* input = new int[n];
	cout << "请对数组赋值: " << endl;;
	for (int i = 0; i<n; ++i)
		cin >> input[i];     
	mergeSort(input, 0, n - 1);  
	cout << "合并排序后数组: " << endl;;
	for (int i = 0; i<n; ++i)
		cout << input[i] << " ";
	cout << endl;
	delete []input;
	system("pause");
	return 0;
}

代码参考：http://blog.sina.com.cn/s/blog_4d3a41f401010jbf.html

运行结果：