递归的本质 逻辑上自己调用自己 系统上帮你压栈
比如我要解决一个问题A 我必须先解决他的子问题B B也有子问题C C也有........
相当于一种依赖的关系 递归 去回
耗内存 效率低 一切递归可以改成非递归
master公式
T（N）= T（N/2）+0（N）
待续
归并 mergeSort
分而治之
从上往下 分
先将左部分与右部分排好序（递归行为排序）；
一个辅助数组
左与右比较 谁小往辅助数组里填 直到填完一部分 （越界） 将另一部分的剩余填进辅助数组 再返回原数组
java中Arrays.sort()采用了一种名为TimSort的排序算法，就是归并排序的优化版本。归并每次合并操作的平均时间复杂度为O(n)，而完全二叉树的深度为|log2n|。总的平均时间复杂度为O(nlogn)。而且，归并排序的最好，最坏，平均时间复杂度均为O(n*logn)。
小和问题 从下往上的归并 逆序列问题
原文：https://www.cnblogs.com/yonkki/p/10193404.html