5.比較排序之歸併排序（非遞歸）

　　在上一節中講解了歸併排序的遞歸版《4.比較排序之歸併排序（遞歸）》，通常來講，遞歸版的歸併排序要更為常用，本節簡單介紹下非遞歸版的歸併排序。思路和遞歸版相同，均為先分解後合併，非遞歸的重點在於如何確定併合理的分解待排序數組。
　　對於遞歸我們是這麼做的：

　　對於非遞歸來講，切分的不向遞歸從大到小，非遞歸實際上從一開始構建演算法的時候都從小到大。

　　第一次切分排序就確定最小單位為1個數字，將2個數字組合為一組。

　　第二次切分排序確定為2個數字，將4個數字組合為一組。

　　第三次切分排序確定為4個數字，將8（7）個數字組合為一組。

　　也就是說非遞歸歸併排序中分解的依據為：從切分的水長度為1開始，一次歸併變回原來的2倍。每完成一次歸併則 len = len * 2。

　　Java

 1 package com.algorithm.sort.mergenonrecursive;
 2 
 3 import java.util.Arrays;
 4 
 5 /**
 6  * 歸併排序（非遞歸）
 7  * Created by yulinfeng on 2017/6/24.
 8  */
 9 public class Merge {
10 
11     public static void main(String[] args) {
12         int[] nums = {6, 5, 3, 1, 7, 2, 4};
13         nums = mergeSort(nums);
14         System.out.println(Arrays.toString(nums));
15     }
16 
17     /**
18      * 歸併排序（非遞歸）
19      * 從切分的數組長度為1開始，一次歸併變回原來長度的2倍
20      * @param nums 待排序數組
21      * @return 排好序的數組
22      */
23     private static int[] mergeSort(int[] nums) {
24         int len = 1;
25         while (len <= nums.length) {
26             for (int i = 0; i + len <= nums.length; i += len * 2) {
27                 int low = i, mid = i + len - 1, high = i + 2 * len - 1;
28                 if (high > nums.length - 1) {
29                     high = nums.length - 1; //整個待排序數組為奇數的情況
30                 }
31                 merge(nums, low, mid, high);
32             }
33             len *= 2;
34         }
35         return nums;
36     }
37 
38     /**
39      * 將切分的數組進行歸併排序，同遞歸版
40      * @param nums 帶排序數組
41      * @param low 左邊數組第一個元素索引
42      * @param mid 左邊數組最後一個元素索引，mid + 1為右邊數組第一個元素索引
43      * @param high 右邊數組最後一個元素索引
44      */
45     private static void merge(int[] nums, int low, int mid, int high) {
46         int[] tmpArray = new int[nums.length];
47         int rightIndex = mid + 1;
48         int tmpIndex = low;
49         int begin = low;
50         while (low <= mid && rightIndex <= high) {
51             if (nums[low] <= nums[rightIndex]) {
52                 tmpArray[tmpIndex++] = nums[low++];
53             } else {
54                 tmpArray[tmpIndex++] = nums[rightIndex++];
55             }
56         }
57         while (low <= mid) {
58             tmpArray[tmpIndex++] = nums[low++];
59         }
60         while (rightIndex <= high) {
61             tmpArray[tmpIndex++] = nums[rightIndex++];
62         }
63         while (begin <= high) {
64             nums[begin] = tmpArray[begin++];
65         }
66     }
67 }