以夢為馬，不負韶華

引入：

如何將兩個有序數組（假設為升序）合并為一個有序數組？

雙指針法，如果第一個數組的第一個元素大于第二個數組的元素，就取第二個（即較小的那個放在合并的數組的首位置），然后在比較第一個數組第一個元素與第二個數組的第二個元素，以此類推，終將有一個數組的元素先被訪問完，剩下的那個數組的元素一定是大于已經排序后的數組，直接將未排完序的數組的元素添加到我們要合并數組即可。

代碼如下

while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[index++] = a[begin1++];}else{tmp[index++] = a[begin2++];}}while (begin1 <= end1){tmp[index++] = a[begin1++];}while (begin2 <= end2){tmp[index++] = a[begin2++];}

---

實現原理

?歸并排序就是利用上邊的思想進行排序，將無序的數組不斷折中至最短，并在合并的過程中將兩個數組進行合并并排序。其是建立在歸并操作上的一種有效的排序方式，采用分治法，將已經排好序的子序列合并，得到完全有序的序列，在歸的過程中將待排序的數組分為各個小塊，在并的過程中不斷使每個小區間變為有序，最終使該數組有序。
過程刨析

問題引出：

能否在原數組進行排序？

• 如果直接進行數據覆蓋的話明顯不可以，會將未修改的元素覆蓋，直接修改了數組元素，這種想法必然是錯誤的。
• 聰明的同學會想到那么我用交換的形式呢？

看下邊這種情況

?第二個小數組區間已經排好的序已經被打亂，在后邊的排序中，比較時就是先和5比，再和4比，這就違反了我們兩個有序數組分別從第一個元素比大小將小的那個放在合并的數組的第一個位置的核心思想。

?引出空間復雜度，順便也說一說他的時間復雜度，我想大家已經有所猜測了，畢竟和二分法沾邊的算法。
空間復雜度：
?使用歸并排序的方法時要開一份同樣大小的數組裝載這個新數組，比較時用原數組，放置時用開好的新數組。因為遞歸時空間可以復用，所以歸并排序的空間復雜度明顯是O(N)。
時間復雜度：
?時間復雜度是容易判斷，由遞歸的深度和判斷的次數即可得出歸并排序的時間復雜度，二分法將遞歸深度變為log(N)，數據量為N，故時間復雜度為O(N*logN)。

遞歸實現：

void MergeSort(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perroe("malloc fail");return;}_MergeSort(a, tmp, 0, n - 1);free(tmp);
}
void _MergeSort(int* a, int* tmp, int begin, int end)
{if (end <= begin)return;int mid = (end + begin) / 2;MergeSort(a, tmp, begin, mid);MergeSort(a, tmp, mid + 1, end);//歸并到tmp數組，再拷貝回去//a->[begin,mid][mid+1,end]->tmp拷貝過去，新開空間int begin1 = begin, end1 = mid;int begin2 = mid + 1, end2 = end;int index = begin;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[index++] = a[begin1++];}else{tmp[index++] = a[begin2++];}}while (begin1 <= end1){tmp[index++] = a[begin1++];}while (begin2 <= end2){tmp[index++] = a[begin2++];}memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}

?要注意遞歸的結束條件已經想要用遞歸來做什么，不斷分化小區間，然后調用小區間的歸并，直至每個數組只有一個元素，然后再用兩個有序數組合并為一個有序數組的方法，將兩個數組合并。

?上圖展開中好似前半段和后半段的排序是同時進行的，其實不然，根據代碼就可以看出，遞歸先排序好數組的前半部分，再排序數組的后半部分。

?在分割時是有順序的，如果遞歸的過程還是不夠清晰可以自己嘗試畫一畫遞歸展開圖，也可移步二叉樹問題詳談遞歸對遞歸的過程獲得更大的理解和掌握。

---

迭代實現

無疑是借助==循環（迭代）==來實現。
?仔細想一想我們會發現，在遞歸的過程中我們需要的是不斷獲得分割后每一小區間數組的坐標，分割直至每一個小數組只有一個元素為止，然后一個數組有兩個元素，然后繼續合并為八個元素，直至數組的每個坐標的值都被訪問一遍為止。

?如果大家已經看了快速排序的非遞歸版，可能會想到用棧來實現，然而這里用棧是不能解決這里的問題的，快速排序可以用棧是因為數組個數end在使用之后就pop出棧也沒有影響，然而歸并排序還需要知道劃分的范圍最后要合并數組，然而如果想要實現遞歸的過程，前邊的數據都已經被pop掉，無法確定數組范圍，就無法借此來合并。

如動圖所示：

當然，如果一定要用棧或隊列來實現他，會很麻煩，因為有更好的方法可以解決。
要跳出遞歸的思路，利用循環的方法，歸并的思想。
如圖所示

首先一個一個元素排序合并，兩個兩個元素進行排序并合并，兩兩排序后，每兩個元素就變成有序的了，然后四個四個合并并排序，然后八個和八個，這樣就將數組所由元素利用歸并的方式進行排序。

void MergeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}int gap = 1;while (gap < n){for (int i = 0; i < n; i += 2 * gap){int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + 2 * gap - 1;//[begin1,end1]  [begin2,end2]歸并//如果第二組不存在，這一組就不用歸并啦if (begin2 >= n){break;}//如果第二組越界if (end2 >= n){end2 = n - 1;}int index = i;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[index++] = a[begin1++];}else{tmp[index++] = a[begin2++];}}while (begin1 <= end1){tmp[index++] = a[begin1++];}while (begin2 <= end2){tmp[index++] = a[begin2++];}memcpy(a + i, tmp + i, (end2 - i + 1) * sizeof(int));}printf("\n");gap *= 2;}free(tmp);
}

下邊是上述代碼的解釋：

?可以看到，起始條件下gap的值為1，第一次循環時，將begin1為0，end1為0，begin2為1，end2為1。
判斷大小，將小的放前邊，大的放后邊，最后歸并到原數組。

memcpy(a + i, tmp + i, (end2 - i + 1) * sizeof(int));

?由于i=0。拷貝回原數組時，a+i還是a的位置，拷貝數量在-0+1后變為了2，就將判斷后的兩個元素歸并到原數組，且已經排好了序。

• 然后下次循環，i+2,指向了數組第三個元素。
  begin1=2,end1=2,begin2=3,end2=3。
  ?這時就是第二個元素第三個元素排序歸并，直至走完這一次for循環，gap*=2，回到外層while循環，gap<n繼續走，此時gap為2，再次進入for循環時，每次跳躍的間隔就是2，就實現了上邊所說，將數組依次分為一個和一個排序歸并，兩個兩個排序歸并，然后4個和4個歸并。。。。。。

注意：這里while結束的條件為gap>n，在循環內，一定會出現這樣的情況，雖然gap的值沒有大于n，但在for循環中，i的值加等于二倍的gap，所以begin2一定會大于n，這就會造成越界訪問，這時就不應該繼續執行循環，直接break出去，然后在while循環結尾，gap會*=2，當gap的值大于n時，就代表數組已經排序完了。

//如果第二組不存在，這一組就不用歸并啦if (begin2 >= n){break;}

?還有一種情況就是begin2沒有越界，然而end2越界，這時第二個數組還是存在的，直接將end2更改為n-1即可。

if (end2 >= n)
{end2 = n - 1;
}

穩定性分析：

?歸并排序是一個穩定的排序，除了空間復雜度比較大，其他的都是優點，通過上邊的演示，可以發現，在歸并的過程中相同數據的位置排列不會發生變化。

總結：

?歸并排序是一種很不錯的排序方式，如果追求高效率且需要穩定性，歸并排序是首當其沖的最優解，對于當前的計算機來說花費一點內存不算什么，歸并排序的思想很簡單，困難的是細節的把握，相對于其他相同時間復雜度的其他排序方式，大都是不穩定的，所以總體而言歸并排序在排序界還是有一席之地的。

今天的內容就到這里，歡迎大家留言反饋。