归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。值得注意的是归并排序是一种稳定的排序方法。速度仅次于快速排序，为稳定排序算法，一般用于总体无序，但是各子项相对有序的数列。若将两个有序表合并成一个有序表，称为二路归并。

1、算法思想

比较a[i]和a[j]的大小，若a[i]≤a[j]，则将第一个有序表中的元素a[i]复制到r[k]中，并令i和k分别加上1；否则将第二个有序表中的元素a[j]复制到r[k]中，并令j和k分别加上1，如此循环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。

归并排序的算法我们通常用递归实现，先把待排序区间[s,t]以中点二分，接着把左边子区间排序，再把右边子区间排序，最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。

基本思路就是将数组分成二组A，B，如果这二组组内的数据都是有序的，那么就可以很方便的将这二组数据进行排序。如何让这二组组内数据有序了？可以将A，B组各自再分成二组。依次类推，当分出来的小组只有一个数据时，可以认为这个小组组内已经达到了有序，然后再合并相邻的二个小组就可以了。这样通过先递归的分解数列，再合并数列就完成了归并排序。

（1）分治法的三个步骤

设归并排序的当前区间是R[low..high]，分治法的三个步骤是：
①分解：将当前区间一分为二，即求分裂点         
②求解：递归地对两个子区间R[low..mid]和R[mid+1..high]进行归并排序；
③组合：将已排序的两个子区间R[low..mid]和R[mid+1..high]归并为一个有序的区间R[low..high]。

递归的终结条件：子区间长度为1（一个记录自然有序）。

2、代码实现：

package sort;

public class MergingSort {
    public static void main(String[] args) {
        int[] a = {3, 2, 5, 4, 1};
        sort(a, 0, a.length - 1);
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
    }

    public static void sort(int[] data, int left, int right) {
        if (left < right) {
            // 首先找出中间的索引
            int center = (left + right) / 2;
            // 对左边的数组进行递归,使左边有序
            sort(data, left, center);
            // 对中间索引右边的数组进行递归，使右边有序
            sort(data, center + 1, right);
            // 再将二个有序数列合并
            merge(data, left, center, right);
        }
    }

    public static void merge(int[] data, int left, int center, int right) {
        int[] tmpArr = new int[data.length];
        int mid = center + 1;
        // third记录中间数组的索引
        int third = left;
        int tmp = left;
        while (left <= center && mid <= right) {
            // 将两个数组中取出最小的数放入中间数组
            if (data[left] <= data[mid]) {
                tmpArr[third++] = data[left++];
            } else {
                tmpArr[third++] = data[mid++];
            }
        }
        // 剩余部分依次放入中间数组
        while (mid <= right) {
            tmpArr[third++] = data[mid++];
        }
        while (left <= center) {
            tmpArr[third++] = data[left++];
        }
        while (tmp <= right) {
            data[tmp] = tmpArr[tmp++];
        }
    }
}

3、算法分析

1、稳定性
归并排序是一种稳定的排序。

2、存储结构要求
可用顺序存储结构。也易于在链表上实现。

3、时间复杂度
对长度为n的文件，需进行

lgn
趟二路归并，每趟归并的时间为O(n)，故其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlgn)。

4、空间复杂度
需要一个辅助向量来暂存两有序子文件归并的结果，故其辅助空间复杂度为O(n)，显然它不是就地排序。
注意：
若用单链表做存储结构，很容易给出就地的归并排序。

5、比较操作的次数介于(nlogn) / 2和nlogn - n + 1。

6、赋值操作的次数是(2nlogn)。归并算法的空间复杂度为：0 (n)

7、归并排序比较占用内存，但却是一种效率高且稳定的算法。

代码地址：https://github.com/zxiaofan/Algorithm/blob/master/src/sort/MergingSort.java