基本思想
歸并排序（MERGE-SORT）是利用歸并的思想實(shí)現(xiàn)的排序方法撩穿，該算法采用經(jīng)典的分治（divide-and-conquer）策略（分治法將問題分(divide)成一些小的問題然后遞歸求解黄绩，而治(conquer)的階段則將分的階段得到的各答案"修補(bǔ)"在一起，即分而治之)蚜退。
分而治之
可以看到這種結(jié)構(gòu)很像一棵完全二叉樹，本文的歸并排序我們采用遞歸去實(shí)現(xiàn)（也可采用迭代的方式去實(shí)現(xiàn)）利耍。分階段可以理解為就是遞歸拆分子序列的過程望抽，遞歸深度為log2n。
合并相鄰有序子序列
再來看看治階段煌妈，我們需要將兩個(gè)已經(jīng)有序的子序列合并成一個(gè)有序序列儡羔，比如上圖中的最后一次合并，要將[4,5,7,8]和[1,2,3,6]兩個(gè)已經(jīng)有序的子序列璧诵，合并為最終序列[1,2,3,4,5,6,7,8]汰蜘，來看下實(shí)現(xiàn)步驟。
"治" 代碼實(shí)現(xiàn)
圖看完了之宿，現(xiàn)在來看代碼吧族操。
void merge(int *arr, int left, int mid, int right ,int *temp)
{
int i = left;//左序列指針
int j = mid+1;//右序列指針
int t = 0;//臨時(shí)數(shù)組指針
while (( i <= mid) && ( j <= right))
{
if (arr[i] < arr[j])
{
temp[t++] = arr[i++];
}
else
{
temp[t++] = arr[j++];
}
}
while (i <= mid)//將左邊剩余元素填充進(jìn)temp中
{
temp[t++] = arr[i++];
}
while (j <= right)//將右序列剩余元素填充進(jìn)temp中
{
temp[t++] = arr[j++];
}
t = 0;
//將temp中的元素全部拷貝到原數(shù)組中
while (left <= right)
{
arr[left++] = temp[t++];
}
}
這個(gè)函數(shù)有點(diǎn)難理解，我們還是拿上圖的具體例子來說吧比被。執(zhí)行merge(arr, 0, 4, 8, temp)色难，其實(shí)就是把{4,5,7,8}(暫時(shí)稱為左子數(shù)組)和{1,2,3,6}(右子數(shù)組)兩個(gè)已經(jīng)有序的子序列炕婶，合并為最終序列{1,2,3,4,5,6,7,8}。先比較左右子數(shù)組的第一個(gè)元素的大小莱预，把較小的存到臨時(shí)數(shù)組的第一個(gè)元素柠掂，然后把對應(yīng)的子數(shù)組的指針加1，繼續(xù)比較依沮。直到左右子數(shù)組中某一個(gè)子數(shù)組完全被復(fù)制到了temp中涯贞，接下來的while循環(huán)做的事情就是把剩下的子數(shù)組中的剩余元素都復(fù)制進(jìn)temp。由于不知道是左子數(shù)組還是右子數(shù)組剩余元素危喉，所以都要寫一遍宋渔。最后把temp數(shù)組的元素拷貝到arr中，arr就排序好了辜限。
"分" 代碼實(shí)現(xiàn)
void MSort(int *arr, int left, int right, int *temp)
{
// if (left = right) return;
if (left < right)
{
int mid = (left + right) / 2;
MSort(arr, left, mid, temp);//左邊歸并排序皇拣，使得左子序列有序
MSort(arr, mid+1, right, temp);//右邊歸并排序，使得右子序列有序
merge(arr, left, mid, right, temp);//將兩個(gè)有序子數(shù)組合并操作
}
}
"分"采用了遞歸的方法薄嫡，采用了折半的策略氧急，先歸并左子數(shù)組，再歸并右子數(shù)組毫深，再把左右子數(shù)組合并吩坝。有的讀者可能覺得MSort函數(shù)沒有終止條件，其實(shí)它是有的哑蔫，隱含的條件是這個(gè)if (left = right) return;钉寝，因?yàn)楫?dāng)left = right時(shí)，其實(shí)只有一個(gè)元素闸迷，肯定是有序的嵌纲。
歸并排序遞歸版 代碼實(shí)現(xiàn)
// 歸并排序遞歸版
void MergeSort(int *arr, int length)
{
int *temp = (int *)malloc(sizeof(int) * length);//在排序前，先建好一個(gè)長度等于原數(shù)組長度的臨時(shí)數(shù)組腥沽，避免遞歸中頻繁開辟空間
MSort(arr, 0, length-1, temp);
free(temp);
}
歸并排序是穩(wěn)定排序逮走，它也是一種十分高效的排序，能利用完全二叉樹特性的排序一般性能都不會太差巡球。從上文的圖中可看出言沐，每次合并操作的平均時(shí)間復(fù)雜度為O(n)邓嘹，而完全二叉樹的深度為|log2n|酣栈。總的平均時(shí)間復(fù)雜度為O(nlogn)汹押。而且矿筝，歸并排序的最好，最壞棚贾，平均時(shí)間復(fù)雜度均為O(nlogn)窖维。
