我們直接對代碼進(jìn)行分析：
void MERGE_SORT(int A[], int p, int r){??//分離數(shù)據(jù)樹
?int q;
?q = (p + r) / 2;
?if (r - p > 3){
??MERGE_SORT(A, p, q);
??MERGE_SORT(A, q + 1, r);
?}
?MERGE(A, p, q, r);?//排序
}
劃分區(qū)間，注意數(shù)組下標(biāo)從0開始！p,r為劃分?jǐn)?shù)組的起始下標(biāo)和最后一個元素的下標(biāo)，，q為中間下標(biāo),q大于5時進(jìn)行歸并排序，小于5時進(jìn)行插入排序（當(dāng)個數(shù)較少時，用插入排序可以減少遞歸調(diào)用的空間使用，且其效率較高）
具體排序過程：
void MERGE(int A[], int p, int q, int r){??//排序
?if (r - p > 3){
??int n1, n2, i = 0, j = 0, k;????? ?//當(dāng)p=0,q=4,r=9時
??int *L, *R;
??L = new int[NUM];
??R = new int[NUM];
??n1 = q - p + 1;???? //n1=5
??n2 = r - q;??????????? //n2=5
??for (i = 0; i < n1; i++){
???L[i] = A[p + i];????????????????? ?//A[0]開始到A[4]賦給左邊數(shù)組L[0]到L[4]
??}
??for (j = 0; j < n2; j++){
???R[j] = A[q + j + 1];??????????? //A[5]開始到A[9]賦給右邊數(shù)組R[0]到L[4]
??}
??L[n1] = MAX;??????? //設(shè)置哨兵
??R[n2] = MAX;??????? //設(shè)置哨兵
??i = j = 0;
??for (k = p; k <= r; k++){??? //k=p=0,r=9,使十個數(shù)都排列到A[]中
???if (L[i] <= R[j]){?????????????? ?//當(dāng)L[i]比R[j]小時，把L[i]放到A[K]中，反之亦然
????if (j != n2){????????????????? ?//R[j]不等于標(biāo)志位
?????A[k] = L[i];
?????i++;
????}
????else{
?????for (; k <= r; k++){???? //R[j]等于標(biāo)志位時，把剩余的L[i]放到A中
??????A[k] = L[i];
??????i++;
?????}
????}
???}
???else{
????if (i != n1){
?????A[k] = R[j];
?????j++;
????}
????else{
?????for (; k <= r; k++){
??????A[k] = R[j];
??????j++;
?????}
????}
???}
??}
??delete[]L;????? //釋放空間
??delete[]R;
?}
?else{?????????????? ?//插入排序
??int temp, i;
??for (int j=p+1; j <= r; j++){
???temp = A[j];
???i = j - 1;
???while (i >= p && A[i] > temp){
????A[i + 1] = A[i];
????i--;
????A[i + 1] = temp;
???}
??}
?}
}
這種排序方法就像把一副撲克牌分成兩份（牌面向下放置），然后每次從兩疊牌上方各抽一張比較，按順序疊放合并。就是一個完全二叉樹向上合并過程。
具體排序過程（已加入測試方法，具體見源代碼）：
--------分治法：歸并排序加插入排序---------
請輸入排序數(shù)值：
18 12 26 7 28 2 24 23 22 1 20 16 19 3·
本次測試數(shù)組大小：
0 13???????????????????????????? ???????? ???????? //p=0,r=13
--------------------------------------------
左區(qū)間: 0? 6????????????????????? ? ????//第一次劃分區(qū)間（大于5，繼續(xù)劃分）
左區(qū)間: 0? 3????????????????????? ?
???//第二次劃分區(qū)間（小于5，進(jìn)入插入排序）
測試插入排序情況：
7?? 12?? 18?? 26
右區(qū)間: 4? 6????????????????????? ?? ??//完成左區(qū)間，進(jìn)入右區(qū)間劃分，同理進(jìn)行排序，注意，這里是對區(qū)間【4,6】進(jìn)行操作
測試插入排序情況：??? ???//對區(qū)間【4,6】進(jìn)行操作,3個數(shù)據(jù)，插排
7?? 12?? 18?? 26?? 2??
24?? 28?? ?//插排完成，返回數(shù)據(jù)后長度為7（>5），接著進(jìn)行并歸排序
測試并歸排序情況：
2?? 7?? 12?? 18?? 24??
26?? 28
右區(qū)間: 7? 13???????????????????????????? ???? ?//對后7個元素進(jìn)行同樣處理
左區(qū)間: 7? 10
測試插入排序情況：??? //這里排的是23 22 20 1
2?? 7?? 12?? 18?? 24??
26?? 28?? 1?? 20?? 22?? 23
右區(qū)間: 11? 13
測試插入排序情況：
2?? 7?? 12?? 18?? 24??
26?? 28?? 1?? 20?? 22??
23?? 3?? 16?? 19
測試并歸排序情況：
2?? 7?? 12?? 18?? 24??
26?? 28?? 1?? 3?? 16??
19?? 20?? 22?? 23?????//前7個數(shù)據(jù)與后7個再次歸并排序
測試并歸排序情況：
1?? 2?? 3?? 7?? 12??
16?? 18?? 19?? 20?? 22??
23?? 24?? 26?? 28?????//已經(jīng)完成排序
結(jié)果：1? 2? 3? 7? 12? 16? 18? 19?
20? 22? 23? 24? 26? 28
請按任意鍵繼續(xù). . .
利用分治法，可以大大減少重復(fù)比較，但相對地帶來了較大的空間開銷，利用插入排序等其他原址排序能夠很好地減少空間開銷。其運(yùn)行時間主要有：
分解：計算中間值，需要常量時間：
。
解決：分解為規(guī)模為n/2的問題需要2T(n/2)運(yùn)行時間。
合并：在n個元素需要的時間
需要時間的遞歸式：T(n)=2T(n/2)+cn;
其時間復(fù)雜度為：
最后附上源代碼：https://github.com/LRC-cheng/Algorithms_Practise.git
