先写 合并两个有序数组， 然后分治递归
    动画演示：
    https://visualgo.net/zh/sorting

    1. public class MergeSort {
    3.     /**
    4.      * 归并排序
    5.      */
    6.     public static int[] mergeSort(int[] array) {
    7.         if (array.length < 2) {
    8.             return array;
    9.         }
    10.         int mIndex = array.length / 2;
    11.         int[] yin = mergeSort(Arrays.copyOfRange(array, 0, mIndex));
    12.         int[] yang = mergeSort(Arrays.copyOfRange(array, mIndex, array.length));
    13.         System.out.println("yin: " + Arrays.toString(yin) + "--- yang: " + Arrays.toString(yang));
    14.         return merge(yin, yang);
    15.     }
    17.     /**
    18.      * 合并两个有序数组
    19.      * @param yin 数组1
    20.      * @param yang 数组2
    21.      * @return 合并后的有序数组
    22.      */
    23.     public static int[] merge(int[] yin, int[] yang) {
    24.         int i = 0;
    25.         int j = 0;
    26.         int[] result = new int[yin.length + yang.length];
    27.         int rIndex = 0;
    28.         while (i < yin.length && j < yang.length) {
    29.             if (yin[i] < yang[j]) {
    30.                 result[rIndex] = yin[i];
    31.                 i ++;
    32.             } else {
    33.                 result[rIndex] = yang[j];
    34.                 j++;
    35.             }
    36.             rIndex++;
    37.         }
    38.         if (i < yin.length) {
    39.             for (int k = i; k < yin.length; k++, rIndex++) {
    40.                 result[rIndex] = yin[k];
    41.             }
    42.         }
    43.         if (j < yang.length) {
    44.             for (int k = j; k < yang.length; k++, rIndex++) {
    45.                 result[rIndex] = yang[k];
    46.             }
    47.         }
    48.         System.out.println("marge result: " + Arrays.toString(result));
    49.         return result;
    50.     }
    52.     public static void main(String[] args) {
    53.         int[] arr = {2, 33, 443, 3232, 3, 33, 12, -11};
    54.         System.out.println(Arrays.toString(mergeSort(arr)));
    55.     }
    56. }

    输出：

    1. yin: [2]--- yang: [33]
    2. marge result: [2, 33]
    3. yin: [443]--- yang: [3232]
    4. marge result: [443, 3232]
    5. yin: [2, 33]--- yang: [443, 3232]
    6. marge result: [2, 33, 443, 3232]
    7. yin: [3]--- yang: [33]
    8. marge result: [3, 33]
    9. yin: [12]--- yang: [-11]
    10. marge result: [-11, 12]
    11. yin: [3, 33]--- yang: [-11, 12]
    12. marge result: [-11, 3, 12, 33]
    13. yin: [2, 33, 443, 3232]--- yang: [-11, 3, 12, 33]
    14. marge result: [-11, 2, 3, 12, 33, 33, 443, 3232]