陆兴毕
针对你的问题：
为什么归并排序merge sort不需要像动态规划的问题一样考虑每一种划分情况？
我的分析如下：
递归的重要性不言而喻，它是很多算法实现的基础，比如含有分治思想的算法（归并排序，二分查找），有关遍历二叉树的算法，或者求解数学递推式的算法（斐波那契数列，n的阶乘），回溯法，动态规划等等， 一提到递归总有点发蒙，理论上比较好理解，但是一遇到复杂一点的递归算法，在大脑中很难想象递归在计算机中是怎么实现的。跟着一步步debug才终于搞明白，所以在这里先把过程给记录下来。
归并排序算法：就是运用分治的思想，把排序的过程变为先把数组分成左右两个部分，分别排序，再将排好序的两个数组合并成一个有序数组。
重点分析一下代码中 Merge_sort_c这个递归函数，首先是终止条件p>=r ，递归必须要有终止条件，否则就会陷入循环最终导致栈溢出。为啥会栈溢出？递归调用在底层其实是对线程栈的压栈和出栈操作，每调用一次都会压栈一次，并记录相关的局部变量信息，线程栈的内存是非常有限的，而递归调用如果是无限的，那么很快就会消耗完所有的内存资源，最终导致内存溢出。
接下来是两个调用了Merge_sort_c 函数本身也就是递归调用，将这两个递归调用分别编号#1和#2.在本例中,待排序的数组里面有6个元素(下标0-5)， 那么他们是怎么被压栈又出栈的呢？如下图所示:
往日好食光
首先要了解归并排序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不需要像动态规划的问题一样考虑每一种划分情况。
