– 将两个或两个以上的有序序列合并成一个新的有序序列 注意，这里是需要有序序列才能合并！！！！！
– 首先我们要知道，当某个序列只有一个元素的时候，这个序列肯定是有序的，这就是我们的突破口，同时这也 是归并排序递归的出口。 – 将一个无序的序列分成两路，不断重复这个拆分操作，直到所有序列都有序。
– 多个有序序列合成一个新的有序序列其实很简单，这里以两路为例。记录两路的序列当前元素的坐标为起始位 置，比较两者大小，大的（或者小的）放入辅助空间，然后被放入的那个序列的当前位置后移。 – 当其中一个序列全都放入辅助空间后，剩下的一个序列的元素直接放入辅助空间。 – 当然辅助空间是辅助排序用的，最后还是得把排序好的序列放回原序列。
店小二上代码！！ 来嘞
template<typename T> void Merge(T array[],T helper[],int begin,int mid,int end,bool min2max) { int help_b = begin; int left_b = begin; int right_b = mid+1; //使两路有序序列合成一个有序序列，两个序列可能长度不相同，会导致有部分没有进入辅助空间 while( (left_b<=mid) && (right_b<=end) ) { if( min2max ? array[left_b]<array[right_b] : array[left_b]>array[right_b] ) { // helper[help_b] = array[left_b]; // help_b++; // left_b++; helper[help_b++] = array[left_b++]; } else { // helper[help_b] = array[right_b]; // help_b++; // right_b++; helper[help_b++] = array[right_b++]; } } //保证左边的都放入了辅助空间 while (left_b<=mid) { helper[help_b++] = array[left_b++]; } //保证右边的都放入了辅助空间 while (right_b<=end) { helper[help_b++] = array[right_b++]; } //把辅助空间中的序列放到原数组 for(int i = begin;i<=end;i++) { array[i] = helper[i]; } } template<typename T> void Merge(T array[],T helper[],int begin,int end,bool min2max = true) { if(begin!=end) { int mid = (begin + end)/2; Merge(array,helper,begin,mid,min2max); Merge(array,helper,mid+1,end,min2max); //真正的归并操作 Merge(array,helper,begin,mid,end,min2max); } } template<typename T> void Merge(T array[],int len,bool min2max = true) { T* help = new T[len]; Merge(array,help,0,len-1,min2max); delete help; }归并排序需要额外的辅助空间帮助完成，空间复杂度为 O(n) 归并排序的时间复杂度为 O(n*logn) , 是一种稳定的排序法
