从排序开始（三）归并排序
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
归并操作的过程如下：
1.申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
2.设定两个指针，最初位置分别为两个已经排序序列的起始位置
3.比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
4.重复步骤3直到某一指针达到序列尾
5.将另一序列剩下的所有元素直接复制到合并序列尾
简单地说，归并排序就是将序列不断地划分，直到每个序列只有一个元素（一个元素的序列肯定是有序的），然后这些有序序列不断归并，合成新的有序序列，最后，归并成全部有序的序列。
这幅 Wiki 的图很直观地解释了归并排序：
最差时间复杂度 O(n logn)
最优时间复杂度 O(n)
平均时间复杂度 O(n logn)
稳定性：稳定
实现：
#include <iostream>using namespace std;//归并操作，将有两个个有序数列 num[start...mid] 和 num[mid...end] 归并并。//归并至 sorted 序列，然后复制回原数组void merge(int num[], int start, int mid, int end, int sorted[]){int i = start, j = mid + 1;int m = mid, n = end;int k = 0;//每次比较两个元素，直到某个序列到达末尾while (i <= m && j <= n){if (num[i] <= num[j])sorted[k++] = num[i++];elsesorted[k++] = num[j++];}//将序列中剩余元素直接复制到 sorted 序列尾while (i <= m)sorted[k++] = num[i++];while (j <= n)sorted[k++] = num[j++];//将排序好的序列写回原数组for (i = 0; i < k; i++)num[start + i] = sorted[i];}void mergesort(int a[], int start, int end, int sorted[]){if (start < end){//进行分治int mid = (start + end) / 2;mergesort(a, start, mid, sorted); mergesort(a, mid + 1, end, sorted); merge(a, start, mid, end, sorted); }}bool MergeSort(int num[], int n){int *p = new int[n];if (p == NULL)return false;mergesort(num, 0, n - 1, p);delete[] p;return true;}//简单测试,建议数据不要太大，那是在刷屏啊 o(╯□╰)oint main(){int n;//测试 n 个随机数的排序while(cin>>n){int *p = new int[n];if (!p){cout<<"Failed..."<<endl;continue;}for(int i=0;i<n;++i)p[i] = rand();bool flag = MergeSort(p,n);if(!flag){cout<<"Failed..."<<endl;continue;}for(int i=0;i<n;++i)cout<<p[i]<<' ';cout<<endl;delete []p;}return 0;}