结果

image.png

完整代码

package Sort;

/**
 * @author klr
 * @create 2020-07-08-23:13
 */
public class MergeSort {

    public static void main(String[] args) {
        MergeSort mergeSort = new MergeSort();
        int[] array=new int []{2,5,6,1,8,3,9,7};
        int[] temp = new int[array.length];
        mergeSort.split(array, 0, array.length-1, temp);
    }

    public void split(int[] array, int left, int right, int[] temp) {
        if (left < right) {
            int mid=(left+right)/2;
            split(array,left,mid,temp);
            split(array,mid+1,right,temp);
            //不能再分时，比如left=0，right=1，此时前两个为空，到下面，合并0-1，然后2-3，然后0-3
            merge(array,left,mid,right,temp);
        }
    }


    public void merge(int[] array, int left, int mid, int right, int[] temp) {

        int l=left;//第一个子数组
        int j=mid+1;//mid+1为第二个子数组的开头
        int t=0;//temp数组的开始

        while (l<=mid && j<=right){
            if (array[l] <= array[j]) {
                temp[t] = array[l];
                l++;
                t++;
            }
            else {
                temp[t] = array[j];
                j++;
                t++;
            }
        }
        //如果第一个数组还未完
        while (l <= mid) {
            temp[t] = array[l];
            t++;
            l++;
        }
        //如果第二个数组还未完
        while (j <= right) {
            temp[t] = array[j];
            t++;
            j++;
        }
        //整理完大小，把temp移回原数组
        t=0;
        int tempLeft=left;
        System.out.println("left："+left+"，right："+right);

        for (int i : temp) {
            System.out.print(i+" ");
        }
        System.out.println();
        System.out.println();

        while (tempLeft<=right){
            array[tempLeft] = temp[t];
            tempLeft++;
            t++;
        }

    }
}