归并排序，分治的典型应用，归并排序的实现有两种方法
1.自上而下的递归
2.自下而上的迭代
算法思想：
1.申请空间，使其大小为两个已排序序列之和，该空间用来合并后的序列。
2.设两个指针，最初位置分别在两个排序序列的起始位置。
3.比较两个指针所指向的元素，选择相对小的元素放入合并空间，并移动到下一个位置。
4.重复第3步，直到其一个指针到序列的尾项。
5.将另一个序列剩下的所有元素直接复制到合并序列尾部。
6.将合并空间的所有元素复制回原数列中。
代码：
1.递归版
void Merge(vector<int> &array,int front,int mid,int end){
vector<int> left(array.begin()+front,array.begin()+mid+1):
vector<int> Right(array.begin()+mid+1,array.begin()+end+1);
int idxleft=0,idxright=0;
left.insert(left.end(),numeric_limits<int>::max));
Right.insert(Right.end(),numeric_limits<int>::max));
for (int i=front;i<=end;i++){
if (left[idxleft]<Right[idxright])
array[i]=left[idxleft++];
else
array[i]=Right[idxright++];
}
}
void MergeSort(vector<int> &array,int front,int end){
if(front>=end) return ;
int mid=(front+end)/2;
MergeSort(array,front,mid);
MergeSort(array,mid+1,end);
Merge(array,front,mid,end);
}
练习：