最終完成代碼：
void merge(int *a, int l, int m, int r) {
int start1 = l;
int end1 = m;
int start2 = m + 1;
int end2 = r;
int k,i;
k = 0;
int *temp = (int*)malloc((r - l + 1) * sizeof(int));
while (start1 <= end1 && start2 <= end2) {
if (a[start1] < a[start2]) {
temp[k++] = a[start1++];
}
else {
temp[k++] = a[start2++];
}
}
while (start1 <= end1) {
temp[k++] = a[start1++];
}
while (start2 <= end2) {
temp[k++] = a[start2++];
}
for (i = 0; i < (r - l + 1); i++) {
a[l + i] = temp[i];
}
free(temp);
}
void merge_sort(int *a,int l, int r){
int m = (l + r) / 2;
if(l < r){
merge_sort(a,l,m);
merge_sort(a,m+1,r);
merge(a,l,m,r);
}
}
學(xué)習(xí)總結(jié)：
第一個歸并函數(shù)是將兩個有序數(shù)組歸并的函數(shù)，是通過兩兩對比分別插入到新數(shù)組的過程，因此他需要申請一個和原量數(shù)組空間和大小的空間來存放歸并后的數(shù)組，由于該歸并函數(shù)是用于歸并排序的茶鹃，所以其中有一個比較重要的操作，就是將歸并之后的temp數(shù)組在復(fù)制給原數(shù)組艰亮，這樣就可以在歸并排序這個函數(shù)遞歸調(diào)用的時候確保每次調(diào)用的兩個數(shù)組是有序的闭翩，其中歸并排序這個遞歸函數(shù)采用的是分治法，在不滿足條件left <right的情況下迄埃，只有可能是只有一個單一元素的數(shù)組疗韵，因為只有一個元素，因此該數(shù)組一定是有序的侄非，之后就是通過兩兩歸并蕉汪，最終實現(xiàn)最后的排序。
空間及時間復(fù)雜度：
空間：O(n)
時間：O(nlogn)
時間復(fù)雜度圖解分析
計算遞歸式表示的總代價逞怨，我們只要把各層代價加起來肤无，遞歸樹具有l(wèi)gn+1層，每層的代價均為cn骇钦，所以總代價為cn(lgn+1) = cnlgn+cn,即O(nlogn)
穩(wěn)定與否：穩(wěn)定
歸并排序圖解原理
