歸并排序采用分治的方法。 對歸并排序來說： 如果對Merge的每個遞歸調用都聲明一個臨時數組，那么任一時刻可能會有logN個臨時數組處于活動期,這對小內存機器是致命的。另一方面，如果Merge動態分配并釋放最小量臨時空間，那么由malloc占用的時間會很多。由于Merge位于MSort的最后一行，可以在MergeSort中建立該臨時數組。因此在任一時刻只需要一個臨時數組活動，而且可以使用該臨時數組的任意部分；我們將使用和輸入數組array相同的部分。這樣的話，該算法的空間占用為N，N是待排序的數組元素個數。 ~~~ /* tmp_array[]：輔助數組。 left_pos：數組左半部分的游標 left_end：左邊數組的右界限 */ void Merge(int array[], int tmp_array[], int left_pos, int right_pos, int right_end) { int i, left_end, num_elements, tmp_pos; left_end = right_pos - 1; tmp_pos = left_pos; num_elements = right_end - left_pos + 1; while (left_pos <= left_end && right_pos <= right_end) if (array[left_pos] <= array[right_pos]) tmp_array[tmp_pos++] = array[left_pos++]; else tmp_array[tmp_pos++] = array[right_pos++]; while (left_pos <= left_end) tmp_array[tmp_pos++] = array[left_pos++]; while (right_pos <= right_end) tmp_array[tmp_pos++] = array[right_pos++]; for (i = 0; i < num_elements; i++, right_end--) array[right_end] = tmp_array[right_end]; } void MSort(int array[], int tmp_array[], int left, int right) { int center; if (left < right) { center = (left + right) / 2; MSort(array, tmp_array, left, center); MSort(array, tmp_array, center + 1, right); Merge(array, tmp_array, left, center + 1, right); } } void MergeSort(int array[], int n) { int *tmp_array; //上面文字部分給出了為什么在MergeSort中建立臨時數組tmp_array ?tmp_array = (int *)malloc(n * sizeof(int)); if (tmp_array != NULL) { MSort(array, tmp_array, 0, n - 1); free(tmp_array); } else cout << "malloc failed" << endl; } ~~~ 雖然歸并排序的時間為O(NlogN)，但是它很難用于主存排序，因為合并兩個排序的表需要線性附加內存，整個算法中還要花費將數據拷貝到臨時數組再拷貝回來這樣的附加工作，這嚴重影響排序的速度。 對于重要的內部排序應用而言，往往選擇快速排序。合并的方法是大多數外部排序算法的基石。 ------------------------------------------------------分割------------------------------------------------------------------ 空間復雜度為o(1)的歸并排序代碼：github（[點擊打開鏈接](https://github.com/liyangddd/algorithms/blob/master/7mergesort_improved.cpp)） 摘錄如下： ~~~ //空間復雜度為O(1)的歸并排序 #include <iostream> using namespace std; void reverse_array(int a[], int n) { int i = 0; int j = n - 1; while (i < j) { swap(a[i], a[j]); ++i; --j; } } void exchange(int a[], int length, int length_left) { reverse_array(a, length_left); reverse_array(a + length_left, length - length_left); reverse_array(a, length); } void Merge(int a[], int begin, int mid, int end) { while (begin < mid && mid <= end) { int step = 0; while (begin < mid && a[begin] <= a[mid]) ++begin; while (mid <= end && a[mid] <= a[begin]) { ++mid; ++step; } exchange(a + begin, mid - begin, mid - begin - step); } } void MergeCore(int a[], int left, int right) { if (left < right) { int mid = (left + right) / 2; MergeCore(a, left, mid); MergeCore(a, mid + 1, right); Merge(a, left, mid + 1, right); } } void MergeSort(int a[], int length) { if (a == NULL || length < 1) return; MergeCore(a, 0, length - 1); } int main() { int a[] = {1,0,2,9,3,8,4,7,6,5,11,99,22,88,11}; int length = sizeof(a) / sizeof(int); MergeSort(a, length); for (int i = 0; i < length; i++) cout << a[i] << " "; cout << endl; return 0; } ~~~ 下面的文章給出了[在空間復雜度O(1)的條件下實現歸并排序](http://blog.csdn.net/pennyliang/article/details/1269165) 原文如下： 第一：對一個L1,L2,的子序列，分別長度為，m,n.可以用min(m,n)的空間協助進行歸并排 序，且僅對該額外空間的值得順序有影響。詳細參見sara basse的那本算法書. 第二：對于一個已經排序的L1,L2,總長度假定為u,為了方便分析,假定L1的長度=L2的長度=u/2,切分成sqrt(u)的個 塊，每個快有sqrt(u)個數，然后對L1,的最后一塊和L2的最后一塊歸并，L2的最后一 塊存放全部數據的最大數據，同時也是利用L2的這個最后一塊作為下面歸并的額外空間。 第三：對剩余的塊(除L2最后一塊,那塊存放最大元素的那塊),按照塊的最小元素排序，之后依次歸并相鄰塊。 第四：對最后一塊進行排序，因為他作為額外空間，參與了兩兩相鄰的塊排序,自己的順序不能保證,所以最后還要排序一次。 這種方法的正確性可以這樣來簡單解釋 由于最后的分塊都是從L1或者L2中切下來的。 那么第i塊，第i+1塊和第i+2塊（如果按照最小元素排序的話） 不妨假定第i塊來自L1，第i+1塊來自L2。（i，i+1，i+2，是切下來后的編號，例如例子中第1塊是1 4 6 15是L1的第一塊，第2塊2 3 4 16是L2的第1塊） 那么i+2塊可能來自哪里呢？要么是原L1塊在第i塊后面，要么是原L2塊在i+1塊后面的塊。也就是第i+1塊至少比N個數要大（N為塊內數目），換言之i和i+1塊歸并后的最小塊i'塊均比i+1塊小，這一點是本算法的難點，想明白后，就不難理解了。 因此i和i+1這兩塊歸并后的i‘塊的最大元素，一定比i+1塊的最小元素要小，因此正確性可以保證。 畫個圖來舉例：   ???????????????????????????????圖1 通過對L1和L2的最大塊進行歸并，用一個4個元素的交換空間，得到L1&L2的最大塊22 23 24 25  ????????????????????????? 圖2 將歸并順序按照塊最小元素的順序進行歸并，并利用交換空間  圖3 利用交換空間歸并的過程，注意歸并后交換空間的數依然是22 23 24 25，但順序已經變了，因此在歸并到最后還需要再排序一次 4 5 6 15 和?16 17 20?21的歸并不再圖示。