<script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script> # Merge Sort - 歸并排序 -------- #### 問題 用歸并排序對長度為$$ n $$的無序序列$$ s $$進行排序。 #### 解法 本問題對無序序列$$ s $$進行升序排序，排序后$$ s $$是從小到大的。 對于長度為$$ n $$的序列$$ s[0,n) $$，將其從中間分開為$$ left[0,k] $$和$$ right[k+1,n-1] $$兩個部分（$$ 0 \le k \lt n-1 $$），假設$$ left[0,k] $$和$$ right[k+1,n-1] $$兩個部分已經是升序的，那么只需要將這兩個部分進行合并排序即可。設$$ i $$和$$ j $$兩個下標分別從$$ left $$和$$ right $$的最左邊（$$ 0 \le i \le k $$，$$ k+1 \le j \le n-1 $$）向右遍歷，每次將$$ left[i] $$和$$ right[j] $$中較小的值插入新的數組中，即可完成一次合并操作。  遞歸的將$$ left[0,k] $$和$$ right[k+1,n-1] $$分別拆分為更小的$$ left $$和$$ right $$兩部分，假定子部分也是升序的，重復上述操作即可得到有序的$$ left[0,k] $$和$$ right[k+1,n-1] $$。這樣遞歸下去，當某個部分的長度等于1時，可以看作長度為1的有序部分，遞歸結束。 對于長度$$ n $$的序列$$ s $$，每一輪放置所需要的時間為$$ O(n) $$，總共需要$$ log_{2}n $$輪，該算法的時間復雜度為$$ O(n \cdot log_{2}n) $$。 -------- #### 源碼 [MergeSort.h](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/Sort/MergeSort.h) [MergeSort.cpp](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/Sort/MergeSort.cpp) #### 測試 [MergeSortTest.cpp](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/Sort/MergeSortTest.cpp)