11.1：迭代版的mergeSort

11.1：归并非递归实现

 1 // 非递归方法实现
 2     public static void mergeSort(int[] arr) {
 3         if (arr == null || arr.length < 2) {
 4             return;
 5         }
 6         int N = arr.length;
 7         // 步长
 8         int mergeSize = 1;
 9         while (mergeSize < N) { // log N
10 
11             int L = 0;                     // 当前左组的，第一个位置
12             while (L < N) {
13                 int M = L + mergeSize - 1; // 当前左组最后一个元素的位置
14                 if (M >= N) {
15                     break;                 // 左组不够就结束了
16                 }
17                 int R = Math.min(M + mergeSize, N - 1);   //右组最后一个数的位置
18                 //L ... M  M+1 ... R
19                 merge(arr, L, M, R);
20                 L = R + 1;                                //下一个左组的第一个数的位置
21             }
22             // 防止溢出
23             if (mergeSize > N / 2) {  //当N十分靠近int整数最大值mergeSize * 2越界为负数
24                 break;
25             }
26             mergeSize <<= 1;              // 步长 X 2
27         }
28     }