归并排序（Merge Sort）

  归并排序是建立在归并操作上的一种相对高效的排序算法。是一种非常典型的分治策略应用排序算法，简而概括：分而排之，合而并之。
  归并排序，据说是冯·诺伊曼在1945年首次提出。冯·诺伊曼，是现代计算机科学发展史上开天辟地的大佬之一，不单单是计算机领域，这哥们在整个数学、量子力学和经济学中都做出了卓越的贡献，简直超神一般，遥敬大佬：冯先生 long live ！

基本思想

  归并排序其核心即是将待排数据样本，按规则逐次分割成更小样本集合，拆至不能再拆，将最小样本合并为有序序列，如此递归回去，从而最终达到整个数据样本排序的操作。
  其基本思想如图所示：

  我们可以看到，图示很直观的展示了归并排序算法的核心。

## 算法描述
1：把长度为n的数据样本分成两个长度为n/2的子样本；
2：逐次对子样本重复1操作，直至不能再分；
3：对子样本做归并操作使其成为有序序列；
4：逐次对子样本重复3操作，直至所有数据归并完成，排序结束。

## 动图演示

代码实现

import java.util.Arrays;

/**
 * @author :Veiking
 * @version :2020年10月15日 
 * 说明 :归并排序算法
 */
public class MergeSort {
    /**
     * 归并排序入口
     * @param arrays
     * @return
     */
    public static int[] sort(int[] arrays) {
        arrays = division(arrays, 0, arrays.length - 1);
        return arrays;
    }

    /**
     * 归并排序之二分

     * @param arrays
     * @param left
     * @param right
     * @return
     */
    public static int[] division(int[] arrays, int left, int right) {
        int center = (left + right) / 2;
        // 二分左右，进入递归，直到left==right，数组即不能再分
        if (left < right) {
            division(arrays, left, center);
            division(arrays, center + 1, right);
        }
        // 当数组二分不能再分，开始归并排序
        merge(arrays, left, center, right);
        return arrays;
    }

    /**
     * 归并排序之归并
     * @param arrays
     * @param left
     * @param center
     * @param right
     */
    public static void merge(int[] arrays, int left, int center, int right) {
        // 用于暂存小组归并排序后的数组的临时数组
        int[] tempArrays = new int[right - left + 1];
        int i = left;
        int j = center + 1;
        // 临时数组的下标
        int index = 0;
        // 同时循环遍历左右两个数组元素，按大小顺序依次插入到临时数组里
        while (i <= center && j <= right) {
            // 若左边数组的元素较小，则插入到临时数组；若右边数组的元素较小，则插入到临时数组。此行为即为归并的典型操作
            if (arrays[i] < arrays[j]) {
                tempArrays[index] = arrays[i];
                i++;
            } else {
                tempArrays[index] = arrays[j];
                j++;
            }
            index++;
        }
        // 左半边数组多余的数据处理，将左半边多余数据直接追加入临时数组
        while (i <= center) {
            tempArrays[index] = arrays[i];
            i++;
            index++;
        }
        // 右半边数组多余的数据处理，将右半边多余数据直接追加入临时数组
        while (j <= right) {
            tempArrays[index] = arrays[j];
            j++;
            index++;
        }
        // 归并完毕，将临时数组中的数据重新放进原数组
        for (int k = 0; k < index; k++) {
            arrays[left + k] = tempArrays[k];
        }
    }

    // 执行
    public static void main(String[] args) {
        int[] input = new int[] { 3, 6, 9, 5, 13, 15, 4, 11, 1, 12, 16, 2, 14, 10, 7, 8 };
        System.out.println("样本初始样本数据：" + Arrays.toString(input));
        int[] output = MergeSort.sort(input);
        System.out.println("归并排序结果数据：" + Arrays.toString(output));
    }
}

算法分析

  选择排序算法的基本性能，归纳如下图：

1、 时间复杂度

  根据上边分析的图示可以看出，归并排序展开看就像是一棵二叉树，它需要遍历的次数就是这个二叉树的深度，且这个跟待排数据元素是否有序而也无关系，统统都要递归分割、逐次归并，根据完全二叉树的深度，可以得出它的时间复杂度是O(nlog₂n)，最好最坏平均都一样，都是O(nlog₂n)。

2、 空间复杂度

  由上边的说明分析可以知道，每次元素进行归并排序算法处理的时候，都需要用一个长度为n的临时数组用于保存合并序列，故空间复杂度为O（n）。

3、稳定性

  根据归并排序的规则，可以确定的是，无论是数据样本的分割过程还是归并过程，都是临近数据的对比操作，不存在什么不确定性，可以保证等值元素相对位置不发生改变，故归并序也是稳定的算法。