首先要了解歸併排序Merge Sort和動態規劃的定義

歸併排序（MergeSort）演算法，是建立在歸併操作上的一種有效的排序演算法，效率為O(nlogn) 。1945年由約翰·馮·諾伊曼首次提出。該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用，且各層分治遞迴可以同時進行。

實現方式有兩種：

1) 遞迴法: 自頂向下（Top-Down）

直接在原序列上直接歸併排序，每次歸併排序分別對左右兩邊進行歸併排序，直至細分到兩兩分組。

2)迭代法：自底向上（Bottom-Up）

假設序列共有 n 個元素：

1. 先相鄰兩兩分組進行歸併排序

2. 再相鄰四四分組進行歸併排序

3. 再相鄰八八分組進行歸併排序

4. 重複擴大分組規模，直到所有元素排序完畢

複雜度:

平均時間複雜度：O(nlogn)

最壞時間複雜度：O(nlogn)

最優時間複雜度：O(nlogn)

最壞空間複雜度：O(n)

動態規劃演算法

演算法的核心在於找到狀態轉移方程 主問題分解成子問題，自底向上/自頂向下，通往問題的 solution 如果有子問題的重複計算，則可以儲存中間結果，用空間換時間。

綜上，動態規劃核心在於找到狀態轉移方程，並將劃分情況中的重複計算中間結果進行儲存，而歸併排序使用的是分治法，只需要各層分治遞迴，不需要找到狀態轉移方程，更不需要儲存劃分情況中的重複計算中間結果，所以Merge Sort不需要像動態規劃的問題一樣考慮每一種劃分情況。

針對你的問題：

為什麼歸併排序merge sort不需要像動態規劃的問題一樣考慮每一種劃分情況？

我的分析如下：

遞迴的重要性不言而喻，它是很多演算法實現的基礎，比如含有分治思想的演算法（歸併排序，二分查詢），有關遍歷二叉樹的演算法，或者求解數學遞推式的演算法（斐波那契數列，n的階乘），回溯法，動態規劃等等， 一提到遞迴總有點發蒙，理論上比較好理解，但是一遇到複雜一點的遞迴演算法，在大腦中很難想象遞迴在計算機中是怎麼實現的。跟著一步步debug才終於搞明白，所以在這裡先把過程給記錄下來。

歸併排序演算法：就是運用分治的思想，把排序的過程變為先把陣列分成左右兩個部分，分別排序，再將排好序的兩個數組合併成一個有序陣列。

重點分析一下程式碼中 Merge_sort_c這個遞迴函式，首先是終止條件p>=r ，遞迴必須要有終止條件，否則就會陷入迴圈最終導致棧溢位。為啥會棧溢位？遞迴呼叫在底層其實是對執行緒棧的壓棧和出棧操作，每呼叫一次都會壓棧一次，並記錄相關的區域性變數資訊，執行緒棧的記憶體是非常有限的，而遞迴呼叫如果是無限的，那麼很快就會消耗完所有的記憶體資源，最終導致記憶體溢位。

接下來是兩個呼叫了Merge_sort_c 函式本身也就是遞迴呼叫，將這兩個遞迴呼叫分別編號#1和#2.在本例中,待排序的數組裡面有6個元素(下標0-5)， 那麼他們是怎麼被壓棧又出棧的呢？如下圖所示: