简介

归并排序简称 Merge sort 是一种递归思维的排序算法。这个算法的思路就是将要排序的数组分成很多小的局部，直到这些小的局部都是已排序的数组为止（只有一个元素的数组）。

而后将这些排序过的数组两两合并起来，组成一个更大一点的数组。接着将这些大一点的合并过的数组再持续合并，直到排序残缺个数组为止。

归并排序的例子

如果咱们有一个数组：29,10,14,37,20,25,44,15，怎么对它进行归并排序呢？

先看一个动画：

咱们来详细分析一下下面例子的运行过程：

首先将数组分为两局部，[29,10,14,37]和[20,25,44,15]。

[29,10,14,37]又分成两局部 [29,10] 和[14,37]。

[29,10]又被分成两局部 [29] 和[10]，而后对 [29] 和[10]进行归并排序生成[10,29]。

同样的对 [14,37] 进行归并排序失去[14,37]。

将 [10,29] 和[14,37]再次进行归并排序失去[10,14,29,37]，以此类推，失去最初的后果。

归并排序算法思维

归并排序次要应用了分而治之的思维。将一个大的数组分成很多很多个曾经排序好的小数组，而后再对小数组进行合并。

这个 Divide 的过程能够应用递归算法，因为不论是大数组还是小数组他们的 divide 逻辑是一样的。

而咱们真正做排序的逻辑局部是在合并这一块。

归并排序的 java 实现

先看一下最外围的 merge 局部：

   /**
     * 合并两局部已排序好的数组
     * @param array 待合并的数组
     * @param low   数组第一局部的终点
     * @param mid   数组第一局部的起点，也是第二局部的终点 -1
     * @param high  数组第二局部的起点
     */
    private void  merge(int[] array, int low, int mid, int high) {
        // 要排序的数组长度
        int length = high-low+1;
        // 咱们须要一个额定的数组存储排序过后的后果
        int[] temp= new int[length];
        // 分成左右两个数组
        int left = low, right = mid+1, tempIdx = 0;
        // 合并数组
        while (left <= mid && right <= high) {temp[tempIdx++] = (array[left] <= array[right]) ? array[left++] : array[right++];
        }
        // 一个数组合并完了，剩下的一个持续合并
        while (left <= mid) temp[tempIdx++] = array[left++];
        while (right <= high) temp[tempIdx++] = array[right++];
        // 将排序过后的数组拷贝回原数组
        for (int k = 0; k < length; k++) array[low+k] = temp[k];
    }

大家须要留神的是，咱们的元素是存在原始数组外面的，办法的第一个参数就是原始数组。

前面的三个参数是数组中须要归并排序的 index。三个 index 将数组划分成了两局部：array[low to mid], array[mid+1 to high]。

merge 的逻辑就是对这两个数组进行合并。

因为咱们的数组自身是寄存有原始的，所以要想进行归并排序，咱们须要借助一个额定的数组空间 int[] temp。

通过比拟 array[low to mid], array[mid+1 to high]中的元素大小，一个个将元素插入到 int[] temp 中，最初将排序过后的数组拷贝回原数组，merge 实现。

而后咱们再看一下 divide 的局部，divide 局部实际上就是递归调用，在递归的最初，咱们须要调用 merge 办法即可：

    public void doMergeSort(int[] array, int low, int high){// 要排序的数组 array[low..high]
        // 应用二分法进行递归，当 low 的值大于或者等于 high 的值的时候，就进行递归
        if (low < high) {
            // 获取两头值的 index
            int mid = (low+high) / 2;
            // 递归后面一半
            doMergeSort(array, low  , mid);
            // 递归前面一半
            doMergeSort(array, mid+1, high);
            // 递归结束，将排序过后的数组的两局部合并
            merge(array, low, mid, high);
            log.info("merge 之后的数组:{}",array);
        }
    }

array 是原数组，low 和 high 标记出了要递归排序的数组起始地位。

运行下下面的后果：

能够看到输入后果和咱们动画展现的后果是统一的。

归并排序的工夫复杂度

咱们看下归并排序的工夫复杂度是怎么样的。

首先看 merge 办法，merge 办法理论是遍历了两个数组，所以 merge 办法的工夫复杂度是 O(N)。

再看一下 divide 办法：

divide 办法将排序分成了 logN 层，每层都能够看做是对 N 个元素的合并排序，因而每层的工夫复杂度是 O(N)。

加起来，总的工夫复杂度就是 O(N logN)。

本文的代码地址：

learn-algorithm

本文已收录于 http://www.flydean.com/algorithm-merge-sort/

最艰深的解读，最粗浅的干货，最简洁的教程，泛滥你不晓得的小技巧等你来发现！

欢送关注我的公众号:「程序那些事」, 懂技术，更懂你！