时间复杂度：o（nlogn）

    归并算法本质可以理解为二叉树的后序遍历
    归并排序就是先把左半边数组排好序，再把右半边数组排好序，然后把两半数组合并，算法实现的难也就是把两半数组合并

    1. // 定义：排序 nums[lo..hi]
    2. void sort(int[] nums, int lo, int hi) {
    3.     if (lo == hi) {//base case
    4.         return;
    5.     }
    6.     int mid = (lo + hi) / 2;
    7.     // 利用定义，排序 nums[lo..mid]
    8.     sort(nums, lo, mid);
    9.     // 利用定义，排序 nums[mid+1..hi]
    10.     sort(nums, mid + 1, hi);
    12.     /****** 后序位置 ******/
    13.     // 此时两部分子数组已经被排好序
    14.     // 合并两个有序数组，使 nums[lo..hi] 有序
    15.     merge(nums, lo, mid, hi);
    16.     /*********************/
    17. }
    19. // 将有序数组 nums[lo..mid] 和有序数组 nums[mid+1..hi]
    20. // 合并为有序数组 nums[lo..hi]
    21. void merge(int[] nums, int lo, int mid, int hi);

    二叉树问题可以分为两类思路，一类是遍历一遍二叉树的思路，另一类是分解问题的思路，根据上述类比，归并排序利用的是分解问题的思路（分治算法）。
    归并排序的过程可以在逻辑上抽象成一棵二叉树，树上的每个节点的值可以认为是nums[lo..hi]，叶子节点的值就是数组中的单个元素：
    image.png
    然后，在每个节点的后序位置（左右子节点已经被排好序）的时候执行merge函数，合并两个子节点上的子数组：
    image.png
    这个merge操作会在二叉树的每个节点上都执行一遍，执行顺序是二叉树后序遍历的顺序。

    2.     /**
    3.      * 合并左右两个区间
    4.      * @param arr
    5.      * @param l
    6.      * @param mid
    7.      * @param r
    8.      */
    9.     private static void merge(int[] arr, int l, int mid, int r) {
    10.         int[] help = new int[r-l+1];//一个辅助数组存储合并后的元素
    11.         int p1 = l;//左指针
    12.         int p2 = mid + 1;//右指针
    13.         int i = 0;//help的指针
    14.         while (p1 <= mid && p2 <= r){//两个指针都不越界情况下遍历填充help数组
    15.             help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
    16.         }
    18.         //若右指针p2先越界了,那么我就让左指针继续走
    19.         while(p1 <= mid){
    20.             help[i++] = arr[p1++];
    21.         }
    22.         //同理p1越界情况
    23.         while (p2 <= r){
    24.             help[i++]  = arr[p2++];
    25.         }
    26.         //将help的元素刷新到arr
    27.         for (int j = 0; j < help.length; j++) {
    28.             arr[l+j] = help[j];
    29.         }
    30.     }
    public static void mergeSort(int[] arr){

        if (arr == null || arr.length <= 1){
            return;
        }
        process(arr,0,arr.length - 1);
    }
    //递归函数 让arr[L....R]变得有序

    /**
     * 递归实现左右两边有序
     * @param arr
     * @param L
     * @param R
     */
    private static void sort(int[] arr, int L, int R) {
        //终止条件
        if (L == R){
            return;
        }
        int mid =  L + (R - L)/2;
        sort(arr,L,mid);//左边变有序
        sort(arr,mid + 1,R);//右边变有序
        merge(arr,L,mid,R);//让左右两个子序列合并
    }

    /**
     * 合并左右两个区间
     * @param arr
     * @param l
     * @param mid
     * @param r
     */
    private static void merge(int[] arr, int l, int mid, int r) {
        int[] help = new int[r-l+1];//一个辅助数组存储合并后的元素
        int p1 = l;//左指针
        int p2 = mid + 1;//右指针
        int i = 0;//help的指针
        while (p1 <= mid && p2 <= r){//两个指针都不越界情况下遍历填充help数组
            help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }

        //若右指针p2先越界了,那么我就让左指针继续走
        while(p1 <= mid){
            help[i++] = arr[p1++];
        }
        //同理p1越界情况
        while (p2 <= r){
            help[i++] = arr[p2++];
        }
        //将help的元素刷新到arr
        for (int j = 0; j < help.length; j++) {
            arr[l+j] = help[j];
        }
    }