如何实现归并排序？

将每个元素拆分成大小为1的部分

递归地合并相邻的两个数组分区

  i = 左侧开始项指数 到 右侧最后项指数 的遍历（两端包括）

    如果左侧首值 <= 右侧首值

      拷贝左侧首项的值

    否则： 拷贝右侧部分首值

将元素拷贝进原来的数组中

public class MergeSort {

    public static void main(String[] args) {
        int[] arr = {18, 15, 13, 17, 6, 20, 15, 9};
        System.out.println("排序前：" + Arrays.toString(arr));
        mergeSort(arr);
        System.out.println("排序后：" + Arrays.toString(arr));
    }

    public static void mergeSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        process(arr, 0, arr.length - 1);
    }

    public static void process(int[] arr, int L, int R) {
        if (L == R) {
            return;
        }
        int M = L + ((R - L) >> 1);
        System.out.println("递归调用 L--M--R:" + L + "--" + M + "--" + R);
        //左边数组递归
        process(arr, L, M);
        //右边数组递归
        process(arr, M + 1, R);
        merge(arr, L, M, R);
    }

    public static void merge(int[] arr, int L, int M, int R) {
        System.out.println("开始归并 arr[" + L + "~" + M + "]和arr[" + (M + 1) + "~" + R + "]两部分数组");
        //申请一个和arr长度一样的辅助数组
        int[] help = new int[R - L + 1];

        //比较两组数组，谁小先拷贝谁到辅助数组，拷贝之后移动数组指针
        //定义数组指针，LP表示左部分数组指针，RP表示右部分数组指针，i表示辅助数组的指针
        int LP = L;
        int RP = M + 1;
        int i = 0;
        //左右两边数组均不能越界
        while (LP <= M && RP <= R) {
            help[i++] = arr[LP] <= arr[RP] ? arr[LP++] : arr[RP++];
        }
        //任何一边的数组要越界了，就把该部分的数写到help数组
        while (LP <= M) {
            help[i++] = arr[LP++];
        }
        while (RP <= R) {
            help[i++] = arr[RP++];
        }
        //写回到原数组
        for (i = 0; i < help.length; i++) {
            arr[L + i] = help[i];
        }
    }
}

排序前：[18, 15, 13, 17, 6, 20, 15, 9]
递归调用 L--M--R:0--3--7
递归调用 L--M--R:0--1--3
递归调用 L--M--R:0--0--1
开始归并 arr[0~0]和arr[1~1]两部分数组
递归调用 L--M--R:2--2--3
开始归并 arr[2~2]和arr[3~3]两部分数组
开始归并 arr[0~1]和arr[2~3]两部分数组
递归调用 L--M--R:4--5--7
递归调用 L--M--R:4--4--5
开始归并 arr[4~4]和arr[5~5]两部分数组
递归调用 L--M--R:6--6--7
开始归并 arr[6~6]和arr[7~7]两部分数组
开始归并 arr[4~5]和arr[6~7]两部分数组
开始归并 arr[0~3]和arr[4~7]两部分数组
排序后：[6, 9, 13, 15, 15, 17, 18, 20]

public static void mergeSort2(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    //数组长度
    int N = arr.length;
    //定义每部分参与比较数组的长度，初始长度为1
    int mergeSize = 1;
    //只要mergeSize小于N
    while (mergeSize < N) {
        int L = 0;
        while (L < N) {
            int M = L + mergeSize - 1;
            if (M >= N) {
                break;
            }
            int R = Math.min(M + mergeSize, N - 1);
            merge(arr, L, M, R);
            L = R + 1;
        }
        // 为什么需要这个？主要是为了防止溢出，int的最大值是21亿多（2^31-1），
        // 假如此时mergeSize是20亿，运行下面mergeSize*2的时候就会溢出
        if (mergeSize > N / 2) {
            break;
        }
        mergeSize <<= 1;
    }
}

public static void merge(int[] arr, int L, int M, int R) {
    System.out.println("开始归并 arr[" + L + "~" + M + "]和arr[" + (M + 1) + "~" + R + "]两部分数组");
    //申请一个和arr长度一样的辅助数组
    int[] help = new int[R - L + 1];

    //比较两组数组，谁小先拷贝谁到辅助数组，拷贝之后移动数组指针
    //定义数组指针，LP表示左部分数组指针，RP表示右部分数组指针，i表示辅助数组的指针
    int LP = L;
    int RP = M + 1;
    int i = 0;
    //左右两边数组均不能越界
    while (LP <= M && RP <= R) {
        help[i++] = arr[LP] <= arr[RP] ? arr[LP++] : arr[RP++];
    }
    //任何一边的数组要越界了，就把该部分的数写到help数组
    while (LP <= M) {
        help[i++] = arr[LP++];
    }
    while (RP <= R) {
        help[i++] = arr[RP++];
    }
    //写回到原数组
    for (i = 0; i < help.length; i++) {
        arr[L + i] = help[i];
    }
}

排序前：[18, 15, 13, 17, 6, 20, 15, 9]
开始归并 arr[0~0]和arr[1~1]两部分数组
开始归并 arr[2~2]和arr[3~3]两部分数组
开始归并 arr[4~4]和arr[5~5]两部分数组
开始归并 arr[6~6]和arr[7~7]两部分数组
开始归并 arr[0~1]和arr[2~3]两部分数组
开始归并 arr[4~5]和arr[6~7]两部分数组
开始归并 arr[0~3]和arr[4~7]两部分数组
排序后：[6, 9, 13, 15, 15, 17, 18, 20]