歸并排序的基本思想是：利用遞歸和分而治之（Divide and Conquer）的方法將待排序的數(shù)組劃分成越來越小的局部數(shù)組更米，再對局部數(shù)組排序朴恳，最后利用遞歸的方法將已經(jīng)排序完畢的局部數(shù)組整合成越來越大的有序數(shù)組抄罕。歸并排序包括兩個步驟：
一、分割(Divide)于颖；
二呆贿、整合(Conquer)：
首先來看一下歸并排序中用到的下標(biāo)：left 指局部數(shù)組開頭的元素，right 指局部數(shù)組末尾+1 的元素森渐，mid 是 left 和 right 相加除以2做入，對結(jié)果向下取整。
歸并排序中用到的下標(biāo).png
接下來我們通過對數(shù)組 {9, 6, 7, 2, 5, 1, 8, 4, 2} 對歸并排序進行說明：
歸并排序.jpg
一同衣、分割
向下的藍(lán)色箭頭代表分割竟块，箭頭邊的數(shù)字表示處理順序，分割由mergeSort負(fù)責(zé),當(dāng)局部數(shù)組只剩下一個元素時耐齐，mergeSort不做任何處理直接結(jié)束浪秘，如果不是蒋情，則計算數(shù)組的中央位置 mid, 將 left 到 mid (不包含mid)視作前半部分，mid 到 right (不包含right)視作后半部分耸携，再分別套用mergeSort棵癣；具體步驟如下所示：
Step 1: left=0, right=9, 因此 mid=4, 調(diào)用mergeSort進行分割，將0~4（即9夺衍、6狈谊、7、2）視作前半部分沟沙，河劝；
Step 2: left=0, right=4, 因此 mid=2, 調(diào)用mergeSort進行分割，將0~2（即9尝胆、6）視作前半部分丧裁；
Step 3: left=0, right=2, 因此 mid=1, 調(diào)用mergeSort進行分割，將0~1（即9）視作前半部分含衔，此時局部數(shù)組只剩一個元素煎娇，mergeSort不做任何處理直接結(jié)束；
Step 4: left=1, right=2, 將1~2（即6）視作后半部分贪染，此時局部數(shù)組只剩一個元素缓呛，mergeSort不做任何處理這節(jié)結(jié)束；
Step 5: 接下來對對 {6} 和 {9} 這這兩個局部數(shù)組進行合并杭隙，因此就有了第二個步驟哟绊。
二、整合
向上的橘色箭頭代表整合痰憎，箭頭邊的數(shù)字表示處理順序票髓，整合由merge負(fù)責(zé)。為了方便敘述铣耘，在這里將包含 n1 個元素的前半部分已排序數(shù)組稱為 L洽沟，包含 n2 個元素的后半部分有序數(shù)組稱為 R, 現(xiàn)在我們需要將 L 和 R 中的元素按照升序排列復(fù)制到數(shù)組 A 中，在這里我們可以利用已排序的性質(zhì)進行合并蜗细，同樣我們舉個例子進行說明裆操。
合并兩個已排序的數(shù)組.jpg
Step 5: 調(diào)用merge對前半部分?jǐn)?shù)組和后半部分?jǐn)?shù)組進行合并，結(jié)果為6炉媒、9踪区；
Step 6: left=0, right=4, 因此 mid=2, 調(diào)用mergeSort進行分割，將2~4（即7吊骤、2）視作后部分缎岗；
step 7: left=2, right=4, 因此 mid=3 調(diào)用mergeSort進行分割，將2~3（即7）視作前半部分白粉，此時局部數(shù)組只剩一個元素密强，mergeSort不做任何處理這節(jié)結(jié)束茅郎；
Step 8: left=3, right=4, 將3~4（即2）視作后半部分，此時局部數(shù)組只剩一個元素或渤，mergeSort不做任何處理這節(jié)結(jié)束系冗；
Step 9: 接下來調(diào)用merge對 {7} 和 {2} 這兩個局部數(shù)組進行合并，結(jié)果為 {2薪鹦、7}掌敬；
Step 10: 調(diào)用merge對 {6, 9} {2, 7}這兩個局部數(shù)組進行合并，結(jié)果為 {2, 6, 7, 9}池磁；
Step ........: 以此類推奔害。
Step 24: 最終得到排序的結(jié)果為 {1, 2, 2, 4, 5, 6, 7, 8, 9}。
接下來貼上代碼：
<pre>
void merge(int A[], int n, int left, int mid, int right){
int n1 = mid - left;
int n2 = right - mid;
for (int i = 0; i < n1; i++) L[i] = A[left+i];
for (int i = 0; i < n2; i++) R[i] = A[mid + i];
L[n1] = R[n2] = SENTINEL;
int i = 0, j = 0;
for (int k = left; k < right; k++){
cnt++;
if (L[i] <= R[j]){
A[k] = L[i++];
}
else{
A[k] = R[j++];
}
}
}
//歸并排序
void mergeSort(int A[], int n, int left, int right){
if (left + 1 < right){
int mid = (left + right) / 2;
mergeSort(A, n, left, mid);
mergeSort(A, n, mid, right);
merge(A, n, left, mid, right);
trace(A, n);
}
}
</pre>
運行結(jié)果：
運行結(jié)果.png
穩(wěn)定性：歸并排序包含不相鄰元素間的比較地熄，但并不會直接交換华临，在合并兩個已排序數(shù)組的時候，如果遇到了相同元素端考，只要保證前半部分?jǐn)?shù)組優(yōu)先于后半部分?jǐn)?shù)組雅潭，相同元素的順序就不會顛倒，因此歸并排序?qū)儆诜€(wěn)定的排序算法却特。
復(fù)雜度：在merge處理中扶供，合并算法的復(fù)雜度為O(n1+n2)，對于本例的輸入{9, 6, 7, 2, 5, 1, 8, 4}包含9個元素裂明，若想將其分割成僅包含一個元素的局部數(shù)組椿浓，需要經(jīng)歷9-5-3-2-1的4次分割，總共分為5層闽晦，如果是8個元素扳碍，則分為4層。一般來說n個數(shù)據(jù)大致分為log2(n)層仙蛉。由于每層執(zhí)行merge的復(fù)雜度為O(n)笋敞， 因此歸并排序的整體復(fù)雜度為O(nlogn)。
總結(jié)：歸并排序算法雖然高效穩(wěn)定捅儒，但是在處理過程中液样，除了用于保存輸入數(shù)據(jù)的數(shù)組之外振亮，還需要臨時占用一部分內(nèi)存空間巧还。
