归并排序,是一种分治算法。利用递归，将一个大的数据集合分解成小的子集合。将子集合排好序后，再合并起来。归并排序不是原地排序算法,因为它使用到了临时空间，这也是归并排序没有快速排序应用广泛的主要原因，虽然归并排序的时间复杂度，最好、最坏都是O(logn)。但是，这个也看使用场景，如果在空间换时间的场合，个人认为这种算法也有一定的用武之处。下面看一下java的代码实现

public static void main(String[] args) {
        int[] arr = new int[]{10, 7, 8, 9, 1, 5};
        mergeSort(arr, arr.length);
        System.out.println(Arrays.toString(arr));
    }

    private static void mergeSort(int[] arr, int n) {
        mergeSortInternally(arr, 0, n - 1);
    }

    private static void mergeSortInternally(int[] arr, int p, int r) {
        if (p >= r) {
            return;
        }
        //find middle point
        int q = p + (r - p) / 2;
        //递归分解数组元素下标,处理前半部分
        mergeSortInternally(arr, p, q);
        //处理后半部分
        mergeSortInternally(arr, q + 1, r);

        mergeBySentry(arr, p, q, r);
    }
    /**
    * 普通的合并算法
    */
    private static void merge(int[] arr, int p, int q, int r) {
        //左半个数组的开始下标
        int i = p;
        //右半个数组的开始下标
        int j = q + 1;
        //临时数组的起始下标
        int k = 0;
        //初始化一个和当前分裂好的数组相同大小的临时数组
        int[] temp = new int[r - p + 1];
        while (i <= q && j <= r) {
            //比较左右两个数组的起始值,较小的元素放在临时数组的第一个位置
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }
        //分裂好的两个数组,很可能不是平均分配,所以可能会有一个数组先遍历完成,
        //另外一个数组还有未进行比较数据,此时直接将未进行比较的数组的数据添加到临时数组即可
        //初始化下标,先将下标初始化为左半部分的数组
        int start = i;
        int end = q;
        //说明右半部分未比较完,此时将下标再重置为右半部分的数组
        if (j <= r) {
            start = j;
            end = r;
        }
        //将未比较完的有序数组直接添加到临时数组中
        while (start <= end) {
            temp[k++] = arr[start++];
        }
        //将临时数组的数据拷贝到原数组中
        for (i = 0; i <= r - p; i++) {
            arr[p + i] = temp[i];
        }
    }

    /**
     * 添加了哨兵节点的合并算法
     *
     * @param arr
     * @param p
     * @param q
     * @param r
     */
    private static void mergeBySentry(int[] arr, int p, int q, int r) {
        //初始化左边数组对应的临时空间,增加一个哨兵节点的位置
        int[] leftArr = new int[q - p + 2];
        //初始化右边数组对应的临时空间,增加一个哨兵节点的位置
        int[] rightArr = new int[r - q + 1];

        //将原数组中,左边的数据拷贝到临时数组中
        for (int i = 0; i <= q - p; i++) {
            leftArr[i] = arr[p + i];
        }
        //左边数组增加哨兵节点
        leftArr[q - p + 1] = Integer.MAX_VALUE;
        //将原数组中,右边的数据拷贝到临时数组中
        for (int i = 0; i < r - q; i++) {
            rightArr[i] = arr[q + 1 + i];
        }
        //右边数组增加哨兵节点
        rightArr[r - q] = Integer.MAX_VALUE;
        int i = 0;
        int j = 0;
        int k = p;
        while (k <= r) {
            //左节点小于右节点时,将排好序的临时空间数据加入到原数组中,当i到达哨兵节点时,i不再增加,只增加j即可.
            if (leftArr[i] <= rightArr[j]) {
                arr[k++] = leftArr[i++];
            } else {
                arr[k++] = rightArr[j++];
            }
        }
    }

这里面的关键点是合并函数的实现逻辑，我贴出了2种合并函数的实现。
一种是：原始的合并实现，方法名是：merge
另一种是改良版本，增加了哨兵节点，方法名是：mergeBySentry。
改良版本，明显更容易理解一点。在临界值的情况，大家注意使用哨兵节点，可以让代码逻辑更清晰。

上一篇快速排序java实现，我们聊了一下快速排序的实逻辑，这2种排序经常会在一起进行比较，大家觉着这2种实现逻辑有什么区别吗？最主要的区别是：
归并排序是先将大问题拆解成小问题，然后处理小问题，最后将小问题合并。
快速排序是先处理小的排序区间，然后慢慢处理大问题。
两种排序原理截然不同

（归并排序的代码主要来自于极客时间<数据结构与算法之美>的专栏，大家对算法感兴趣的，可以订阅一下这个专栏，专栏质量很高）