十大经典排序之一的归并，很多资料里都是用了递归，其实递归都能转化为非递归，非递归不会栈溢出，也能更直观看出时间复杂度为O(n*log(n))。
思路很简单，用一个变量span表示跨度，每次跨度*2来循环数组的长度，在循环里再2个span2个span地遍历完数组进行归并。
废话不多上代码：
package class03;
/**
* @Description 归并排序非递归
* @Package: class02
* @Author: Ray
* @CreateTime: 2020/7/4 15:28
* @E-mail: 634302021@qq.com
*/
public class Test7 {
public static void mergeSort(int[] arr) {
if (arr == null || arr.length == 1) { //空或一个数直接返回
return;
}
//初始跨度为1
int span = 1;
while (span < arr.length) {
//for循环里每2个span进行截取出left,mid,right,然后merge排序
for (int i = 0; i < arr.length; i += 2 * span) {
int left = i;
int mid = left + span - 1; //2个跨度进行归并，mid为1个跨度的位置
/*
处理边界，当最后一个mid定位超出了长度，表示最后几个数凑不到一个span，
本次span长度=上次while里span2倍，故也凑不齐上次while循环里的2*span，
凑不齐上次循环2个span的几个数在上次while里一定归并排序好了，
所以可以直接break
*/
if (mid >= arr.length - 1) {
break;
}
int right = left + 2 * span - 1;
if (right >= arr.length - 1) { //处理边界，右边界超出长度则直接为最后一位，这个应该好理解
right = arr.length - 1;
}
merge(arr, left, mid, right); //每个范围归并排序
}
//span = span << 1; //优化一下可以用位运算左移，等同于乘2
span = span * 2; //跨度翻倍，翻倍变为2，4，8，16……从而以log（N）次循环整个数组长度
}
}
//对排完序的left ~ mid, mid+1 ~ right范围进行归并排序
public static void merge(int[] arr, int left, int mid, int right) {
int[] tmp = new int[right - left + 1]; //临时数组
int l = left; //左指针初始位置
int m = mid + 1; //右指针初始位置
int i = 0; //tmp下标
while (l <= mid && m <= right) { //任意左或右指针到边界则退出
if (arr[l] > arr[m]) {
tmp[i] = arr[m];
m += 1;
} else {
tmp[i] = arr[l];
l += 1;
}
i += 1;
}
while (l <= mid) { //如果左指针先循环完，剩下的数补到tmp上
tmp[i] = arr[l];
l += 1;
i += 1;
}
while (m <= right) { //如果右指针先循环完，剩下的数补到tmp上
tmp[i] = arr[m];
m += 1;
i += 1;
}
for (int j = 0; j < tmp.length; j++) { //tmp还原到原数组
arr[left + j] = tmp[j];
}
}
public static void main(String[] args) {
int[] arr = {5, 1, 4, 2, 7, 6, 3, 9, 8};
mergeSort(arr);
Arrays.toString(arr);
}
}
