自底向上，自顶向下，归并排序 的 递归，非递归

归并排序

Merge为归并算法的核心操作，优先介绍，
即将两个已排序的数组合并到一个新的数组中的操作。

归并排序可分为自顶向下与自底向上两种方法。
其中自顶向下是指先将整个数组二分切割，再将切割得到后的子数组二分切割，直至所有子数组仅包含1个元素，之后再进行逐层Merge合并，因此最好使用递归实现。

自底向上上是指，一开始就将整个数组执行：
将相邻的2元素Merge， 将相邻的4元素Merge … 直至整个数组均Merge完毕即排序完毕。

Merge

//将arr中，low——mid 与mid+1——high 合并
    public static void merge(int[] arr, int low, int mid, int h) {
        //left:左子数组起始下标，right:右子数组起始下标  x:arr上更新的下标
        int left = low, right = mid + 1, x = low;
        int[] tmp = new int[arr.length];
        //拷贝数组
        System.arraycopy(arr, 0, tmp, 0, arr.length);
        //终止条件最好用x 而不要用left,right
        while (x <= h) {
            if (left > mid ) {//当left超过mid代表left中用完
                arr[x++] = tmp[right++];
            } else if (right > h ) { //当right过h代表right中用完
                arr[x++] = tmp[left++];
            } else {
                if (tmp[left] <= tmp[right]) {//选小的，若为>= 则为升序排序
                    arr[x++] = tmp[left++];
                } else {
                    arr[x++] = tmp[right++];
                }
            }
        }
    }

自顶向下（递归）

//自顶向下
    public static void Sort(int[] arr, int l, int h) {
        int len = h - l + 1; //最恶心的地方莫过于 -1
        if (len <= 1) {  //终止条件，当长度 <=1 直接返回（意味着开始merge）
            return;
        } else {
            int m = (l + h) / 2;  //自动向下取整，无所谓
            Sort(arr, l, m);  //排序l-m
            Sort(arr, m + 1, h); //排序m+1-h
            merge(arr, l, m, h); //合并
        }
    }

自底向上（非递归）

     //自底向上
    public static void Sort(int[] arr) {
        int length = arr.length;
        int len = 0; //为了最后一次的归并，把len单独定义
        //用len控制窗口大小，将窗口内的两个子数组merge
        for ( len = 2; len <= length; len = len * 2) {//窗口为长度2,4,8...
            //j推动窗口移动
            // 因此窗口中两个数组分别为  [j,j+len/2-1]   [(j+len/2),j+(len-1)]
            // 注意终止条件为第一个子数组的末尾小于数组长度(被包含)，过滤掉不够一组的情况
            for (int j = 0; j + len / 2 - 1 < length; j += len) {
                if (j + len / 2 - 1 < length && j + len - 1 >= length) {
                    //一组健全，一组残废
                    merge(arr, j, j + len / 2 - 1, length - 1);
                } else {
                    //两组健全
                    merge(arr, j, j + len / 2 - 1, j + len - 1);
                }
            }
        }
        //看这里！！需要找到目前排序的长度，用到了‘len’，
        // 最后把所有归并一次
        merge(arr, 0, len / 2 - 1, length - 1);
    }

其中最需要注意的即为非递归中的限制条件与下标，与终止条件的判断。
存在两个易错点：

1. 数量与下标差1：当需要x个元素时，下标之差为x-1;
   eg: 若a[i]-a[j] 代表2个元素，i-j=1

2. 数组尾标与长度：数组尾标与长度总是差1导致终止条件易写错，这里我们可以把 "< length" 即作为在数组内来用，而>=length为超过数组长度的判断，不能丢掉等号。
   因此，如想要写条件“数组内包含一组半”即：
   (j+len/2-1<length && j+len-1>=length)
   全部代码：

import java.util.Arrays;

//归并排序
public class MergeSort {

    //将arr中，low——mid 与mid+1——high 合并
    public static void merge(int[] arr, int low, int mid, int h) {
        //left:左子数组起始下标，right:右子数组起始下标  x:arr上更新的下标
        int left = low, right = mid + 1, x = low;
        int[] tmp = new int[arr.length];
        //拷贝数组
        System.arraycopy(arr, 0, tmp, 0, arr.length);
        //终止条件最好用x 而不要用left,right
        while (x <= h) {
            if (left > mid ) {//当left超过mid代表left中用完
                arr[x++] = tmp[right++];
            } else if (right > h ) { //当right过h代表right中用完
                arr[x++] = tmp[left++];
            } else {
                if (tmp[left] <= tmp[right]) {//选小的，若为>= 则为升序排序
                    arr[x++] = tmp[left++];
                } else {
                    arr[x++] = tmp[right++];
                }
            }
        }
    }

    //自顶向下
    public static void Sort(int[] arr, int l, int h) {
        int len = h - l + 1; //最恶心的地方莫过于 -1
        if (len <= 1) {  //终止条件，当长度 <=1 直接返回（意味着开始merge）
            return;
        } else {
            int m = (l + h) / 2;  //自动向下取整，无所谓
            Sort(arr, l, m);  //排序l-m
            Sort(arr, m + 1, h); //排序m+1-h
            merge(arr, l, m, h); //合并
        }
    }

    //自底向上
    public static void Sort(int[] arr) {
        int length = arr.length;
        int len = 0; //为了最后一次的归并，把len单独定义
        //用len控制窗口大小，将窗口内的两个子数组merge
        for ( len = 2; len <= length; len = len * 2) {//窗口为长度2,4,8...
            //j推动窗口移动
            // 因此窗口中两个数组分别为  [j,j+len/2-1]   [(j+len/2),j+(len-1)]
            // 注意终止条件为第一个子数组的末尾小于数组长度(被包含)，过滤掉不够一组的情况
            for (int j = 0; j + len / 2 - 1 < length; j += len) {
                if (j + len / 2 - 1 < length && j + len - 1 >= length) {
                    //一组健全，一组残废
                    merge(arr, j, j + len / 2 - 1, length - 1);
                } else {
                    //两组健全
                    merge(arr, j, j + len / 2 - 1, j + len - 1);
                }
            }
        }
        //看这里！！需要找到目前排序的长度，用到了‘len’，
        // 最后把所有归并一次
        merge(arr, 0, len / 2 - 1, length - 1);
    }


    public static void main(String[] args) {
        int[] arr = {2, 5, 1, 3, 4};
//        Sort(arr, 0, arr.length - 1);
        Sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}