算法描述：

① 把长度为n的输入序列分成两个长度为n/2的子序列；

② 对这两个子序列分别采用归并排序；

③ 将两个排序好的子序列合并成一个最终的排序序列。

image.png

import java.util.Arrays;

public class MergeSort {
    public static void main(String[] args) {

        System.out.println("=====归并排序=====");
        int[] array = new int[]{10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
        System.out.println("排序之前：");
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }

        //归并排序
        array = mergeSort(array);

        System.out.println("\n");
        System.out.println("排序之后：");
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
    }

    public static int[] merge(int[] left, int[] right) {
        int[] temp = new int[left.length + right.length];
        int i = 0;
        int j = 0;
        int k = 0;

        while (k < temp.length) {
            if (i >= left.length) {
                temp[k++] = right[j++];
            } else if (j >= right.length) {
                temp[k++] = left[i++];
            } else if (left[i] > right[j]) {
                temp[k++] = right[j++];
            } else {
                temp[k++] = left[i++];
            }
        }
        return temp;
    }

    public static int[] mergeSort(int[] arr) {
        if (arr.length < 2)
            return arr;
        int mid = arr.length / 2;
        int[] left = Arrays.copyOfRange(arr, 0, mid);
        int[] right = Arrays.copyOfRange(arr, mid, arr.length);

        return merge(mergeSort(left), mergeSort(right));
    }
}