今天要来讲的是归并排序，同时介绍一关于递归时间复杂度计算公式 —— Master 公式：
首先我们根据图片来看看归并排序的排序思路是怎么样：（我在图右边标上了红色的 0 1 2 3）
首先归并排序会先将一个数组分成拆分成左组和右组，无限拆分，直到左右组都只剩一个元素开始合并，我们可以看到第0层表示的那层。这里就用到了分而治之的思想。
然后我们开始合并，合并的思路是，我们会先申请一个新的数组，如果左组小于等于右组，我们就将左组放进新数组中，如果右组的数字小于左组我们就将右组的数字放进新的数组中。因此新合并的数组一定是有序的！！！这时候我们就来到了第一层，合并完之后变成
如果了解递归的小伙伴会知道，我们用的是深度优先遍历的，所以当我们到达了一层之后，我们还会继续往下走，到第二层，这时候第二层接收到
，我们还需要右边2个数，这时候程序会往下递归到达第一层位置，第一层这时候没有接收到参数，这时候需要继续往下递归递归到最小子情况。当我们到达0层的时候进行返回 5 7进行步骤2中的排序，排序成了[5, 7]。然后接下来的过程也是一样的，递归到最小子数组，然后左右数组合并，直到所有数组排序完毕。
递归的其实就是树的深度优先遍历，所以如果对这里理解有些困难的人可以到我之前写的深度优先遍历的文章里先去找找灵感，然后再回过头来看这个文章，你肯定有不一样的理解。这里还是贴一下递归的顺序图。上面红色线的部分是是正常递归的顺序，在回溯的过程中，递归里面元素的状态会渐渐变得和下面的一样。
接下来我们来看看代码：
先总结一下代码思路：
总共有三个函数：主函数mergeSort，用来调用递归函数process，process会将每个数组分解成最小单个数组元素，然后merge函数将最小单位的左组和右组整合起来。
代码中需要注意的是最下面两个while的部分，注释上有详细解释
public static void mergeSort(int[] arr){
// 主函数用来调用递归函数
if(arr == null || arr.length < 2){ // 边界条件处理，等于null的或者长度为1的就没有必要排序了
return;
}
// 调用递归函数，分解数组 // arr是你想要排序的对象
process(arr, 0, arr.length - 1);// 0 到 arr.length - 1代表你想要排序的范围
}
public static void process(int[] arr, int L, int R){
if(L == R){ // 递归函数结束条件，当左右两边的指针都指向同一个数字的时候
// 就说明数组中只剩下一个元素了，所以需要进行返回了
return;
}
// 我们需要给我们的递归函数传入他需要排序的范围，所以我们从中间开始分解
int mid = L + ((R - L) >> 1); // 这里等于 (L+R)/2 是等价的，写哪个都无所谓
process(arr, L, mid); // 调用递归函数传入范围
process(arr, mid + 1, R);
merge(arr, L, mid, R); // 当递归函数将数组所有元素都分解完毕，我们开始按照规则合并他们
}
public static void merge(int[] arr, int L, int mid, int R){
// 我们处理的是原函数的L 到 R位置，例如是3 位置到 5位置，我们需要处理的长度就是
// 3 4 5 这三个元素，也就是至少申请长度为3的数组，就是右下标 - 左下标 + 1
int[] help = new int[R - L + 1]; // 申请额外的新数组来存储合并的值
int p1 = L; // 左组从 L开始 到mid位置
int p2 = mid + 1; // 右组从 mid + 1开始到 R位置
int i = 0; // 这里是表示新创建数组的index
while(p1 <= mid && p2 <= R){
// 这里的意思是，如果左组的数字小于等于右组的数字则加入左组的数字然后 左组指针的位置+1
// 如果左组的数字大于右组的数字则加入右组的数字，右组指针++
help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
}
// 注意！当我们上面的循环break之后，有可能出现右组指针先达到条件break
// 和左组指针先达到条件然后break，所以我们需要单独的对他们进行处理
while(p1 <= mid){ // 这里处理的是左组
help[i++] = arr[p1++];
}
// 右组与上面同理
while(p2 <= R){
help[i++] = arr[p2++];
}
// 然后将help数组的中的值和原数组的值对应进行替换。使得原数组达到有序的状态
for(i = 0; i < help.length; i++){
arr[L + i] = help[i];// 原数组的元素被处理的范围是从L开始的到R结束
// 所以原数组的下标要从L开始
}
}
然后我们来看看归并函数的时间复杂度和空间复杂度：
要计算归并排序的时间复杂度和空间复杂度，我们首先来了解一下Master公式（当然还有其他很多种方法可以计算，这里介绍其中一种方法）
首先我们来看看Master公式的公式：
我们先来看看公式上的 a b n d都分别表示什么意思：
n表示输入数据的规模
a表示递归的次数也就是生成的子问题数
b表示每次计算的问题的规模
d表示合并左右组所花费的时间
请注意：很重要的一点是我们使用master公式只用计算第一次的流程就行了什么意思？我们现在来解释
在这问题中我们我们生成子问题的次数是2，把一开始输入数据的拆分成等分的左右两份所以我们的生成子问题数a就是2，
同时我们每次递归计算问题的规模是
除去递归行为外我们还需要多长时间的，我们需要的时间复杂度，举个例子：每次传入n长度的数组我们就需要合并n长度的数组，所以
所以d等于 1
因此当我们知道，之后我们根据下面的判别式
我们就能得到归并排序的时间复杂度是。
额外空间复杂度是，因为递归排序回溯时每次都需要申请一个与待排序数组相同长度的数组，所以我们我们最多申请N长度的数组，也就是回溯的最后一步的时候。因此我们按最差的额外空间复杂度去计算也就是
Reference：
https://italk.mashibing.com/course/detail/cour_00004003
https://blog.csdn.net/qq_32595453/article/details/79516787#
