归并排序（点击查看图示）

/*
 * 归并排序
 *
 * 思想：
 *      1、递归进行分裂直到剩1个
 *      2、然后两边依次比较（若从小到大排序，就把小数据放到新数组）
 *      3、最后判断数值内是否有遗留数据，全部放到新数组的后面中
 *
 * */
public class MergeSort {

    public static void main(String[] args) {

        int[] array = {16, 21, 37, 45, 21, 24, 33};

        System.out.println(Arrays.toString(MargeSort(array,0,array.length-1)));

    }

    static void Marge(int[] array,int low,int mid,int high) {
        int[] arrayCopy = Arrays.stream(array).toArray();
        int i,j,k=low;
//       为i,j复制并做出跳出循环的条件
        for (i = low, j = mid + 1; i <= mid && j <= high; k++) {
//          左边元素小于右边元素,把左边元素放进新数组
            if (arrayCopy[i] <= arrayCopy[j]) {
                array[k] = arrayCopy[i++];
            } else {
//          否则将右边元素,放入新数组
                array[k] = arrayCopy[j++];
            }
        }
//      循环判断左右两边的数组是否有遗留的元素
        while (i <= mid) array[k++] = arrayCopy[i++];
        while (j <= high ) array[k++] = arrayCopy[j++];

    }
    static int[] MargeSort(int[] array,int low,int high){
//      递归分裂
        if (low<high){
            int mid=(low+high)/2;
            MargeSort(array,low,mid);
            MargeSort(array,mid+1,high);
//          对比排序
            Marge(array,low,mid,high);
        }

        return array;
    }

}