归并排序
算法思路：
1、将整个序列递归分解为不可分解的单元素序列，这时各个单元素序列有序（递推过程）
2、再将各个单元素序列二路归并（回归过程）
C++：
template <typename T>
void merge(T arr[],int low,int mid,int high){
//复制到一个临时数组
T temp[high - low + 1];
for (int i = low; i <= high; i++) {
temp[i-low] = arr[i];
}
//i和j分别指示两个有序序列的开始
int i = 0,j = mid + 1 - low;
//挑出小的归并到arr，同时移动索引，从临时数组中往arr中复制
for (int k = low; k <= high; k++) {
//保证索引有效性
if (i > mid - low) {
arr[k] = temp[j++];
}else if (j > high - low){
arr[k] = temp[i++];
}else if (temp[i]<temp[j]) {
arr[k] = temp[i++];
}else{
arr[k] = temp[j++];
}
}
}
//归并排序
template <typename T>
void mergeSort(T arr[],int low,int high){
if (high>low) {
int mid = low + (high - low)/2;
mergeSort(arr, low, mid);
mergeSort(arr, mid+1, high);
merge(arr, low, mid, high);
}
}
