5、归并排序（Merge Sort）

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

5.1 算法描述

• 把长度为n的输入序列分成两个长度为n/2的子序列；
• 对这两个子序列分别采用归并排序；
• 将两个排序好的子序列合并成一个最终的排序序列。

5.2 动图演示

5.3 代码实现

/**
 * @author cai-xiansheng
 * @Description 归并排序
 * @create 2021-01-16 16:50
 */
public class MergeSort {

    /**
     * 都是：nlogn
     * @param arr
     * @return
     */
    public static int[] mergeSort(int[] arr) {
        int len = arr.length;
        if (len < 2)
            return arr;
        int mid = (int) Math.floor(len / 2);
        int[] left = new int[mid];
        int[] right = new int[len - mid];
        System.arraycopy(arr, 0, left, 0, mid);
        System.arraycopy(arr, mid, right, 0, len - mid);
        return merge(mergeSort(left), mergeSort(right));
    }

    private static int[] merge(int[] left, int[] right) {
        int[] result = new int[right.length + left.length];
        int r = 0;
        int l = 0;
        for (int i = 0; i < result.length; i++) {
            if (r >= right.length) {
                result[i] = left[l++];
            } else if(l >= left.length) {
                result[i] = right[r++];
            } else if(right[r] >= left[l]) {
                result[i] = left[l++];
            } else if(right[r] < left[l]) {
                result[i] = right[r++];
            }
        }
        return result;
    }
}