通常是通過二分法達到logn這樣一個層級傀蚌，然后每一層級用O(n)級別的算法合并.
歸并排序需要額外的存儲空間來完成排序
i,j指向的是當前正在考慮的元素辣往，k表示需要放的位置 最左邊的元素l,最右邊的元素r, 中間這個位置放在第一個 排好序的數組的最后一個位置叫m.
代碼部分：
template<typename T>
void mergeSort(T arr[], int n){
__mergeSort( arr, 0 ,n-1 );
//對數組的不同部分做歸并 ,該區(qū)間為前閉后閉.
}
// 遞歸使用歸并排序,對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的話，相加可能發(fā)生溢出.
//對左右兩個部分分別進行歸并排序.
__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(wèi)的偏移
//這里要說一下，這個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++;
}
}
}
測試歸并排序：
