该算法采用经典的D&C策略，也就是法治策略。
对比python的分治，Java不能实现对数组的切割，所以本质上是对指针的分割，是对操作区间的分割，要理解索引的变化
基本思路
首先要理解，上面图示中的分并不是真的将数组切割了，只是将操作区间切割了，本质上就是指针的变化范围。
来看怎么治，看治的最后一步，数据多，比较容易理解。原理其实就是运用了中间数组，运用两个索引分别遍历两个部分的元素，值较小的就进入中间数组，大的那个则留下了继续和接下来的数比较，最后如果一边的数全部遍历完了，那另一边的数则自动归入中间数组，图解如下：
代码如下，注意事项已在代码中标明
//合并的方法
public static void merge(int[] arr,int left,int mid,int right,int[] temp){
int i = left;//初始化i，左边有序序列的初始索引
int j = mid + 1;//初始化j，右边有序序列的初始索引
int t = 0;//指向temp数组的当前索引
//（一）
//先把左右两边（有序）的数据按照规则填充到temp数组
//直到左右两边的有序序列，有一边处理完毕为止
while (i <= mid && j<= right){//继续
//如果左边的有序序列的当前元素，小于等于右边有序序列的当前元素
//就将左边的当前元素，填充到temp，然后t++,i--
if (arr[i] <= arr[j]){
temp[t] = arr[i];
t += 1;
i += 1;
}else {
temp[t] = arr[j];
t += 1;
j += 1;
}
}
//（二）
//吧有剩余数据的一边的数据依次全部填充到temp
while (i <= mid){
temp[t] = arr[i];
t += 1;
i +=1;
}
while (j <= right){
temp[t] = arr[j];
t += 1;
j += 1;
}
//（三）
//将temp数组的元素拷贝到arr
t = 0;
int tempLeft = left;
while (tempLeft <= right){
arr[tempLeft] = temp[t];
t += 1;
tempLeft += 1;
}
}
}
这一部分还算好理解，接下来就是递归的部分，先看代码
//分+合的方法
public static void mergeSort(int[] arr,int left,int right,int[] temp){
if (left < right){
int mid = (left+right)/2;
//向左递归进行分解
mergeSort(arr, left, mid, temp);
//向有右递归进行分解
mergeSort(arr,mid+1, right, temp);
//合并
merge(arr,left,mid,right,temp);
}
}
debug理解一下
public void test5(){
int[] arr = {4,8,6,2,9,7,7,21,6,3,5,8};
//Sort.quickSort(arr,0,arr.length-1);
int[] temp = new int[arr.length];
Sort.mergeSort(arr,0,arr.length-1,temp);
System.out.println(Arrays.toString(arr));
}
首先程序会不断运行向左递归，栈里进入了5个mergeSort，注意到在栈顶的方法里，左右指针已经相等，向左递归和向右递归都不会再运行，这时候merge方法得到的就是arr[0]本身，然后整个方法运行完毕，出栈，到第四个方法
则会运行到向右递归，然后向右递归又会进入第五个方法，然后跟上面一样退出，然后进入到第四个方法的merge方法，对4，8运用合并方法进行排序，以此类推，最后当栈内存为空时，则可得到一个排序完成的数组。
最后，本质上这个算法也是一个以空间换时间的极好例子
这个是我听韩老师课的笔记，讲的还不错，感兴趣的同学也可以去听一下，附上链接
【【尚硅谷】数据结构与算法（Java数据结构与算法）-哔哩哔哩】 https://b23.tv/luubUIM
