归并排序小总结（画图理解归并排序）
归并排序小总结（画图理解归并排序）第二次操作之后的数组：第二次干的事：假设一个数组：第一次干的事：第一次操作之后的数组：
归并排序（一）初识篇学习了归并算法，并最终用递归的方式实现了归并算法，但是最后测试贴了一张图，递归的实现还是比较耗时的，接下来学习一下优化的写法。
一、回顾递归实现归并
思路是将数组不断地拆分成两部分，然后将两部分数据进行合并，拆分是递归进行的，这样基于递归的特性，先递进再归来，在归来的时候开始合并操作。
二、为啥不建议用递归
按照上个图的描述，先递进，后归来。合并在归来时完成，那递进不就浪费了一些性能了嘛？而且递归是自己调用自己，会有栈溢出隐患。
递归的方式让我触底了，才能得到左侧为1个数，右侧为1个数的两个数组，才能满足条件，那我可不可以直接就让它满足条件呢？画个图理下思路：
假设一个数组：
第一次干的事：
第一次操作之后的数组：
第二次干的事：
第二次操作之后的数组：
第三次干的事：
第三次操作之后的数组：
这不就完成排序了嘛？其实不然，我做这个数组比较特殊，最后一个是最大的，其实还有一次操作：
老规矩，先画图，画图才能明晰思路：
整理下：
- 我需要一个S，每次乘以2，因为是左右两组比较嘛边界：S一定小于N边界：S一定小于N-L越界：S>N/2，下一次R组的长度可能不够会有越界现象
- 我需要一个L，代表左组的初始位置。
- 我需要一个R，代表右组的初始位置。
上次的merge(int[] arr int L int M int R)，有一个M，M参与了左组，也参与了右组，这次既然还要用这个方法，那么这次：
- 我需要一个M，左组的时候L --> M，右组的时候M 1 --> R边界：M一定小于N边界：R要么是N-1，要么是M S
public static void mergeSort2(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
int N = arr.length;
int S = 1;
while (S < N) {
int L = 0;
while (L < N) {
int M = L S - 1;
if (M >= N) {
break;
}
int R = Math.min(M S N - 1);
merge(arr L M R);
L = R 1;
}
if (S > N / 2) {
break;
}
S <<= 1;
}
}
public static void merge(int[] arr int L int M int R) {
// 我需要一个数组存放数据
int[] narr = new int[R - L 1];
// 我需要三个指针，分别指向三个数据的头
int i = 0;
int p1 = L;
int p2 = M 1;
// 我需要一个循环体 结束条件是其中一个越界了 这里写的是循环条件哦，不是结束条件
// p1 p2都在各自的范围内
while (p1 <= M && p2 <= R) {
narr[i ] = arr[p1] <= arr[p2] ? arr[p1 ] : arr[p2 ];
}
// p1 越界，p1添加完了，剩下数据的就是p2
while (p2 <= R) {
narr[i ] = arr[p2 ];
}
// p2 越界，p2添加完了，剩下数据的就是p1
while (p1 <= M) {
narr[i ] = arr[p1 ];
}
// 合并后的narr数据，要放到原来的数组arr里的
for (int j = 0; j < narr.length; j ) {
// L为左侧数据的开始，从L开始放数据
arr[L j] = narr[j];
}
}
