通常是通过二分法达到logn这样一个层级，然后每一层级用O(n)级别的算法合并.
归并排序需要额外的存储空间来完成排序
i,j指向的是当前正在考虑的元素，k表示需要放的位置 最左边的元素l,最右边的元素r, 中间这个位置放在第一个 排好序的数组的最后一个位置叫m.
代码部分：
template<typename T>
void mergeSort(T arr[], int n){
__mergeSort( arr, 0 ,n-1 );
//对数组的不同部分做归并 ,该区间为前闭后闭.
}
// 递归使用归并排序,对arr[l...r]的范围进行排序
template<typename T>
void __mergeSort(T arr[] ,int l, int r){
if( l >= r ) //数组个数为1或为空
return;
int mid = (l + r) / 2;
//二分查找中，当l r都是非常大的int的话，相加可能发生溢出.
//对左右两个部分分别进行归并排序.
__mergeSort(arr, l, mid);
__mergeSort(arr, mid+1, r);
//合并两个数组
__merge(arr, l, mid, r);
}
//将arr[l...mid]和arr[mid+l...r]两部分进行归并
template<typename T>
void __merge(T arr[], int l, int mid, int r){
T aux[r-l+1];
for( int i = l; i <= r; i++ )
aux[i-l] = arr[i]; //有l的偏移
//这里要说一下，这个i和j是作用在arr上的，但它不是用来操作arr的值的.
//arr的值是通过k来操作的, i和j的作用是用来控制范围同时操作aux数组.
//arr数组的i和j是和aux数组的i-l和j-l同步变化的.
//也可以直接将i和j作用在aux数组上，不过比较麻烦，因为aux的范围是[0, r-l+1]，还要求mid的值，这样式子的值就比较复杂了.
int i = l, j = mid + 1;
for( int k = l; k <= r; k++ ){
//看arr[k]的位置应该放谁
if( i > mid ) {
arr[k] = aux[j-l];
j++;
}
else if( j > r ){
arr[k] = aux[i-l];
i++;
}
else if( aux[i-l] < aux[j-l] ){
arr[k] = aux[i-l];
i++;
}
else{
arr[k] = aux[j-l];
j++;
}
}
}
测试归并排序：
