归并排序

思想：

归并基本思想是将两个（或以上）有序的序列合并成一个新的有序序列。
当然，此处介绍的归并排序主要是将两个有序的数据序列合并成一个新的有序序列。
细化来说，归并排序先将长度为n的无序序列看成是n个长度为1的有序子序列，首先做两两合并，得到 n/2个长度为2的有序子序列，再做两两合并……不断地重复这个过程，最终可以得到一个长度为n的有序序列。

假设有如下数据序列。
21，30，49，30*，97，62，72，08，37，16，54
程序对其不断合并的过程如下图

从图中可以看出，长度为16的数据序列，只需经过4次合并。也就是说，对于长度为n的数据序列，只需经过log2n次合并。
对于归并排序而言，其算法关键就在“合并”。如何将两个有序的数据序列合并成一个新的有序序列？合并算法的具体步骤如下

• 定义变量i，i从0开始，依次等于A序列中每个元素的索引。
• 定义变量j，j从0开始，依次等于B序列中每个元素的索引。
• 拿A序列中i索引处元素和B序列中j索引处的元素进行比较，将较小的复制到一个临时数组中。
• 如果i索引处的元素小，i++；如果j索引处的元素小，j++。

不断地重复上面4个步骤，即可将A、B两个序列中的数据元素复制到临时数组中，直到其中一个数组中的所有元素都被复制到临时数组中。最后，再将另一个数组中多出来的元素全部复制到临时数组中，合并即完成，再将临时数组中数据复制回去即可。

public class MergeSort {

    /**
     * 利用归并排序算法对数组data进行排序
     * @param data
     */
    public static void mergeSort(DataWrap[] data) {
        sort(data, 0, data.length - 1);
    }

    /**
     * 将索引从left到right范围的数组元素进行归并排序
     * @param data
     * @param left  待排序的数组的第一个元素的索引
     * @param right 待排序的数组的最后一个元素的索引
     */
    private static void sort(DataWrap[] 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);
        }
    }

    /**
     * 将两个数组进行归并，归并前两个数组已经有序，归并后依然有序
     * @param data
     * @param left  左边数组的第一个元素的索引
     * @param center    左边数组的最后一个元素的索引，center+1是右边数组第一个元素的索引
     * @param right 右边数组的最后一个元素的索引
     */
    private static void merge(DataWrap[] data, int left, int center, int right) {
        DataWrap[] tmpArr = new DataWrap[data.length];

        int mid = center + 1;
        //third记录中间数组的索引
        int third = left;
        int tmp = left;

        while (left <= center && mid <= right) {
            //从两个数组中取出小的放入中间数组
            if (data[left].compareTo(data[mid]) <= 0) {
                tmpArr[third++] = data[left++];
            }else{
                tmpArr[third++] = data[mid++];
            }
        }

        //把剩余部分依次放入中间数组
        while (mid <= right) {
            tmpArr[third++] = data[mid++];
        }
        while (left <= center) {
            tmpArr[third++] = data[left++];
        }

        //将中间数组中的内容复制拷回原数组
        //原left-right范围的内容被复制回原数组
        while (tmp <= right) {
            data[tmp] = tmpArr[tmp++];
        }
    }

    public static void main(String[] args) {
        DataWrap[] data = new DataWrap[]{
                new DataWrap(9, ""),
                new DataWrap(-16, ""),
                new DataWrap(21, "*"),
                new DataWrap(23, ""),
                new DataWrap(-30, ""),
                new DataWrap(-49, ""),
                new DataWrap(21, ""),
                new DataWrap(30, ""),
                new DataWrap(30, "")
        };

        System.out.println("排序前：\n" + Arrays.toString(data));
        mergeSort(data);
        System.out.println("排序后 ：\n" + Arrays.toString(data));
    }
}

总结

归并排序的时间复杂度为：O(nlog2n)
归并排序算法的空间效率较差，它需要一个与原始序列同样大小的辅助序列
稳定的排序算法