合并排序是一種穩(wěn)定高效的遞歸排序，它是利用分而治之法的解決思路驚醒遞歸排序，合并排序非常穩(wěn)定，時間復(fù)雜度始終都是?O(n log n)，它是一種自上而下的排序方式。

分而治之法：

Divide and conquer，縮寫D&C；它的對事情的解決思路是將事情不斷地縮小至最小，再將他們逐個擊破，最后把問題合并起來解決。它的工作原理是：

1.找出簡單的基線條件；2.確定如何縮小問題的規(guī)模，使其符合基線條件。

合并排序法：

該排序法充分運用到了分而治之的思考方式；在一組數(shù)組中，我們可以將數(shù)組的中間數(shù)作為基線條件，判斷他們大于小于該基線條件，并且放到相應(yīng)的大小數(shù)組中，進行下一次的遞歸。直到數(shù)組不能再次拆解。

圖片來自《圖解算法》

根據(jù)棧的數(shù)據(jù)結(jié)構(gòu)，棧是一種后進先出（Last In First Out，F(xiàn)IFO）的數(shù)據(jù)結(jié)構(gòu)，所以當棧達到最低端的時候，會優(yōu)先返回上圖中的[7,8]數(shù)組，再一層一層往上返回；因此也可以說合并排序是一種由下而上的排序法。再回到最開始所說的D&C思路，正好是最小化問題->解決->合并最小化問題的解決方案。而且這樣做可以減少棧的調(diào)用，且合并排序非常穩(wěn)定，最壞的情況下是O(n log n)，相比起快速排序的最壞情況，因為快速排序極其依賴開發(fā)者對基線條件的選擇，快速排序的最壞情況是O(n的平方)。

至于代碼，沒有代碼！大家可以根據(jù)上述思路實際動手，可以加深理解。在實現(xiàn)遞歸條件時不要忘記臨界點，以免無限堆棧照成死循環(huán)。