一.归并排序原理（Wikipedia)
归并排序本质是分治思想的应用，并且各层分治递归可以同时进行
1.申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
2.设定两个指针，最初位置分别为两个已经排序序列的起始位置
3.比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
4.重复步骤3直到某一指针到达序列尾
5.将另一序列剩下的所有元素直接复制到合并序列尾
二.过程
原始数据
seg = 1时
我的算法参考的是wikipedia上的算法，与VisuAlgo上所示的稍有区别，VisuAlgo上是先2个数字合并，然后合并成4个有序数列，然后在对后面的2个合并，在合并成4个有序数列，把这两组有序数列合并成一个长度为8的有序数列。
wikipedia上，是先将所有的单个数字合并成有序的长度为2的有序数组，然后在将所长度为2的分别合并成长度为4的有序数组，循环知道合成长度为Len的有序数组。个人认为wikipedia上的方法更加容易表达，因为不用回退可以一次性处理完所有相同长度的数据。
wikipedia上代码的排序过程如图所示：
3.代码（参考了wikipedia上的代码，只需要第一次分配一次空间）
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std; template <typename T>
void MergeSort( vector<T> & nums ) {
int seg = ;
int len = nums.size();
vector<T> CopyNums(nums);
for(int seg = ; seg < len; seg += seg ){
for(int start = ; start < len; start += seg + seg ){
int low = start;
int mid = min( start + seg, len );//对于最后一次归并
int high = min( start + seg + seg, len );//最后一次归并长度会大于len
int k = low;
int start1 = low;
int end1 = mid;
int start2 = mid;
int end2 = high;
while( start1 < end1 && start2 < end2 ){
CopyNums[k++] = nums[start1]<nums[start2]? nums[start1++]:nums[start2++];
}
while( start1 < end1 ){
CopyNums[k++] = nums[start1++];//如果start1后还有元素没有归并，则将start1后的元素进行归并
}
while( start2 < end2 ){
CopyNums[k++] = nums[start2++];////如果start2后还有元素没有归并，则将start2后的元素进行归并
}
}
nums.swap(CopyNums);//在C++ STL中，耗时是常量，因为实际并没有交换他们的值，而只是交换了指针。
//(i.e., the containers exchange references to their data, without actually performing any element copy or movement) }
} int main(){
vector<int> nums{,,,,,,,,,,,,,,};
cout<<" Before Sort:" ;
for( auto m: nums){
cout << m <<" ";
}
cout<<endl;
MergeSort( nums );
cout<< " After Sort:";
for( auto m: nums){
cout << m <<" ";
}
cout<<endl;
}
4.总结
1.空间复杂度，因为只有开始分配了一次与原始数据相同长度的空间，所以空间复杂度为O(n);
2.时间复杂度，总的比较次数在(nlogn)/2和nlogn-n+1之间;
3.归并排序是稳定的排序算法。