前言：
    因为排序的种类实在是太多了，放在一篇文章里显得过于冗杂，所以把简单的排序方法放在一起了。
    今天要说的是归并排序，之前我没有接触，或者用过这个排序方式，也可能是我孤陋寡闻了。
    归并排序是1945年由约翰·冯·诺伊曼（John von Neumann）首次提出 。
    原理：
    执行流程 ① 不断地将当前序列平均分割成2个子序列 直到不能再分割（序列中只剩1个元素）； ② 不断地将2个子序列合并成一个有序序列 直到最终只剩下1个有序序列
    image.png
    归并排序的主要步骤分为两个部分，一个是分开，一个是合并

    示例：

    2. protected void sort() {
    3.         leftArray = (T[]) new Comparable[array.length >> 1];
    4.         sort(0, array.length);
    5.     }
    7.     // T(n) = T(n/2) + T(n/2) + O(n)
    9.     /**
    10.      * 对 [begin, end) 范围的数据进行归并排序
    11.      */
    12.     private void sort(int begin, int end) {
    13.         if (end - begin < 2) return;
    15.         int mid = (begin + end) >> 1;
    16.         sort(begin, mid);
    17.         sort(mid, end);
    18.         merge(begin, mid, end);
    19.     }

    当我们已经将数组切开之后，我们该考虑如何让数组有序的合并在一起。
    image.png
    我们将子数组开头第一个数字称之为索引，我们两两比较索引大小，将较小的索引提出，放到新的数组中，去除索引的组数下一位就是新的索引。
    但是，我们可能重新开辟一块新的空间来放置整理好后的数据； 需要 merge 的 2 组序列存在于同一个数组中，并且是挨在一起的，
    image.png
    为了更好地完成 merge 操作，最好将其中 1 组序列备份出来，比如 [begin, mid)
    image.png
    li == 0；le == mid – begin； ri == mid；re == end
    image.png
    我们排序到最后，两边数组总一个会先结束
    当左边先结束的
    image.png
    左边先结束，就是右边有剩余，我们不需要任何操作

    当右边先结束
    image.png
    右边先结束，就是左边有剩余，我们需要将左边剩余部分原封不动的转移过来。

    示例：

    1. private void merge(int begin, int mid, int end) {
    2.         int li = 0, le = mid - begin;
    3.         int ri = mid, re = end;
    4.         int ai = begin;
    6.         // 备份左边数组
    7.         for (int i = li; i < le; i++) {
    8.             leftArray[i] = array[begin + i];
    9.         }
    11.         // 如果左边还没有结束
    12.         while (li < le) {
    13.             if (ri < re && (array[ri]-leftArray[li]) < 0) {
    14.                 array[ai++] = array[ri++];
    15.             } else {
    16.                 array[ai++] = leftArray[li++];
    17.             }
    18.         }
    19.     }

    算法分析：
    ![C}M)4)8036PJVINRMB~9{L.png
    这是一段完整的归并排序代码，可以debug来查看代码运行过程，深入学习
    示例：

    1. public class test {
    2.     private int[] leftArray;
    3.     private int[] array={1,4,2,12,16,19,7,8,3,9};
    6.     public static void main(String[] args) {
    7.         test t=new test();
    8.         t.sort();
    9.         for(int i=0;i<t.array.length;i++){
    10.             System.out.println(t.array[i]);
    11.         }
    12.     }
    15.     protected void sort() {
    16.         leftArray = new int[array.length >> 1];
    17.         sort(0, array.length);
    18.     }
    20.     // T(n) = T(n/2) + T(n/2) + O(n)
    22.     /**
    23.      * 对 [begin, end) 范围的数据进行归并排序
    24.      */
    25.     private void sort(int begin, int end) {
    26.         if (end - begin < 2) {return;}
    28.         int mid = (begin + end) >> 1;
    29.         sort(begin, mid);
    30.         sort(mid, end);
    31.         merge(begin, mid, end);
    32.     }
    34.     /**
    35.      * 将 [begin, mid) 和 [mid, end) 范围的序列合并成一个有序序列
    36.      */
    37.     private void merge(int begin, int mid, int end) {
    38.         int li = 0, le = mid - begin;
    39.         int ri = mid, re = end;
    40.         int ai = begin;
    42.         // 备份左边数组
    43.         for (int i = li; i < le; i++) {
    44.             leftArray[i] = array[begin + i];
    45.         }
    47.         // 如果左边还没有结束
    48.         while (li < le) {
    49.             if (ri < re && (array[ri]-leftArray[li]) < 0) {
    50.                 array[ai++] = array[ri++];
    51.             } else {
    52.                 array[ai++] = leftArray[li++];
    53.             }
    54.         }
    55.     }
    56. }