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

算法描述

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

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

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

归并操作

归并操作(merge)，也叫归并算法，指的是将两个顺序序列合并成一个顺序序列的方法。

设有数列{6，202，100，301，38，8，1}

初始状态：6,202,100,301,38,8,1

第一次归并后：{6,202},{100,301},{8,38},{1}，比较次数：3；

第二次归并后：{6,100,202,301}，{1,8,38}，比较次数：4；

第三次归并后：{1,6,8,38,100,202,301},比较次数：4；

总的比较次数为：3+4+4=11；

逆序数为14；

归并操作的原理

第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列

第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置

第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置

重复步骤3直到某一指针超出序列尾

将另一序列剩下的所有元素直接复制到合并序列尾

代码实现

public class MergeSort {
    private static int count = 1;
    public static void main(String[] args) {
        int[] arr = {8, 4, 5, 7, 1, 3, 6, 2, 9, 10};
        int[] temp = new int[arr.length];
        split(arr, 0, arr.length - 1, temp);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 递归拆分数组然后合并
     *
     * @param arr   待拆分数组
     * @param left  数组左边下标
     * @param right 数组右下标
     * @param temp  用于存放合并后的有序序列的数组
     */
    public static void split(int[] arr, int left, int right, int[] temp) {
        if (left >= right) {
            return;
        }
        System.out.println("拆分第"+(count++)+"次");
        int mid = left + (right - left) / 2;
        //向左拆分
        split(arr, left, mid, temp);
        //向右拆分
        split(arr, mid + 1, right, temp);
        //每次拆分后都执行合并
        merge(arr, left, mid, right, temp);
    }

    /**
     * 合并两个各自有序序列(以mid为界)
     *
     * @param arr   原始数组
     * @param left  数组左边下标
     * @param mid   数组中间下标
     * @param right 数组右边下标
     * @param temp  用于存放新的有序数组
     */
    public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int i = left;
        int j = mid + 1;
        //temp中的原始下标
        int t = 0;

        while (i <= mid && j <= right) {
            //两边数组都没有比较完 继续
            if (arr[i] < arr[j]) {
                //左边数组中值更小
                temp[t] = arr[i];
                i++;
            } else {
                //右边数组中值更小
                temp[t] = arr[j];
                j++;
            }
            t++;
        }
        //有一边已经全部复制到temp中了
        if (i <= mid) {
            //左边还没有复制完，将左边全部元素复制到temp中
            while (i <= mid) {
                temp[t] = arr[i];
                i++;
                t++;
            }
        } else if (j <= right) {
            //右边还没有复制完，将右边全部元素复制到temp中
            while (j <= right) {
                temp[t] = arr[j];
                j++;
                t++;
            }
        }
        //将temp复制到原arr中
        t = 0;
        while (left <= right) {
            arr[left] = temp[t];
            left++;
            t++;
        }
    }
}

复杂度

归并排序把集合一层一层进行折半分组。如果集合长度是n，那么折半的层数就是logn，每一层进行归并操作的运算量是n。所以归并排序的时间复杂度等于每一层的运算量乘以层级数，即O(nlogn)=。
我们再看空间复杂度，由于每次归并所创建的的额外集合都会随着方法的结束而被释放，因此这部分空间不应该累计，单次归并操作开辟的最大的空间是n，所以归并排序的空间复杂度是O(n)。

总结

归并排序的执行原理，主要分为以下步骤：

1.递归的方式进行拆分，将大的数组拆分成小的数组，直到剩余一个不能拆分

2.回溯的时候进行合并，合并时以mid为界，左右两边各自有序，通过额外的空间temp数组，将两个有序数组合并到一个有序数组中

3.将合并后的数组复制到原数组中，当回溯完成时整个数组有序