基本思想
歸并排序采用的是分治算法的思想，其中最重要的操作就是歸并操作哮奇。
主要思想是膛腐，將數(shù)組平分為A睛约，B兩部分，分別將A,B兩部分排好序哲身，然后再合并辩涝，對A排序的時候，也是同樣的思路勘天，將A分為兩份怔揩，同樣先分別排序，再合并脯丝。一直遞歸下去商膊，直到不能再分解為止。
網(wǎng)上看到一張圖很好的解釋了這個過程：
歸并算法過程.png
再用動畫展示一下這個過程：
歸并過程動畫.gif
歸并過程
假設(shè)數(shù)組已經(jīng)被分解成了兩個有序的數(shù)組宠进，這個時候就應(yīng)該將這兩個有序數(shù)組合并成一個新的有序數(shù)組晕拆。這個時候需要額外的存儲空間來輔助這個歸并過程（所以歸并排序不是原地排序）。
下面來張圖展示這個過程：
歸并過程.png
代碼實(shí)現(xiàn)--遞歸版
#include <iostream>
using namespace std;
template<typename T>
void mergeSort(T arr[], int n){
// 一次性申請aux空間,
// 并將這個輔助空間以參數(shù)形式傳遞給完成歸并排序的各個子函數(shù)
T *aux = new T[n];
__mergeSort( arr , aux, 0 , n-1 );
delete[] aux; // 使用C++, new出來的空間不要忘記釋放掉:)
}
// 使用優(yōu)化的歸并排序算法, 對arr[l...r]的范圍進(jìn)行排序
// 其中aux為完成merge過程所需要的輔助空間
template<typename T>
void __mergeSort(T arr[], T aux[], int l, int r){
// 遞歸的終點(diǎn) 數(shù)組只剩一個元素的時候就可以停止了
if( l >= r ){
return;
}
int mid = l + (r-l)/2;
__mergeSort(arr, aux, l, mid);
__mergeSort(arr, aux, mid+1, r);
__merge(arr, aux, l, mid, r);
}
// 將arr[l...mid]和arr[mid+1...r]兩部分進(jìn)行歸并
// 其中aux為完成merge過程所需要的輔助空間
template<typename T>
void __merge(T arr[], T aux[], int l, int mid, int r){
// 將原數(shù)組的數(shù)據(jù)復(fù)制給aux
for( int i = l ; i <= r; i ++ )
aux[i] = arr[i];
// 初始化材蹬，i指向左半部分的起始索引位置l实幕；j指向右半部分起始索引位置mid+1
int i = l, j = mid+1;
for( int k = l ; k <= r; k ++ ){
if( i > mid ){ // 如果左半部分元素已經(jīng)全部處理完畢
arr[k] = aux[j]; j ++;
}
else if( j > r ){ // 如果右半部分元素已經(jīng)全部處理完畢
arr[k] = aux[i]; i ++;
}
else if( aux[i] < aux[j] ) { // 左半部分所指元素 < 右半部分所指元素
arr[k] = aux[i]; i ++;
}
else{ // 左半部分所指元素 >= 右半部分所指元素
arr[k] = aux[j]; j ++;
}
}
}
結(jié)論
歸并排序總的平均時間復(fù)雜度為O(nlogn)，最好赚导，最壞茬缩，平均時間復(fù)雜度均為O(nlogn)。所以歸并排序是穩(wěn)定的排序算法吼旧，缺點(diǎn)是需要額外的存儲空間（貌似也有原地歸并排序凰锡，無需額外存儲空間，待研究）圈暗。
