1.  public static void main(String[] args) {
    2.         int[] arr = {1, 3, 5, 7, 8, 3, 4, 6, 0};
    3.         System.out.println(Arrays.toString(recursiveSort(arr)));
    4.     }
    6.     public static int[] recursiveSort(int[] arr) {
    7.         if (arr == null || arr.length == 1) {
    8.             return arr;
    9.         }
    10.         // 如何将一个数组分成两个合理的数组
    11.         int middleIndex = arr.length / 2; 
    12.         int[] arrLeft = new int[middleIndex];
    13.         int[] arrRight = new int[arr.length - middleIndex];
    14.         for (int i = 0; i < arr.length; i++) {
    15.             if (i < middleIndex) {
    16.                 arrLeft[i] = arr[i];
    17.                 continue;
    18.             }
    19.             arrRight[i - middleIndex] = arr[i];
    20.         }
    21.         return mergeArr(
    22.                 recursiveSort(arrLeft),
    23.                 recursiveSort(arrRight)
    24.         );
    25.     }
    27.     /**
    28.      * 将数组中的元素有序的排列起来
    29.      *
    30.      * @param leftArr  左边的数组 
    31.      * @param rightArr 右边的数组  
    32.      * @return 一个包含左右两个数组的有序数组
    33.      */
    34.     public static int[] mergeArr(int[] leftArr, int[] rightArr) {
    35.         LinkedList<Integer> result = new LinkedList<Integer>();
    36.         // 将左右两个数组 有序的放入这个result数组里面
    37.         LinkedList<Integer> leftList = new LinkedList<>();
    38.         for (int i = 0; leftArr != null && i < leftArr.length; i++) {
    39.             leftList.add(leftArr[i]);
    40.         }
    41. //            Collections.addAll(leftList,leftArr);
    42.         LinkedList<Integer> rightList = new LinkedList<>();
    43.         for (int i = 0; rightArr != null && i < rightArr.length; i++) {
    44.             rightList.add(rightArr[i]);
    45.         }
    46. //            Collections.addAll(rightList,rightArr);
    47.         /**
    48.          *   每一次回来的数组都是排好顺序的
    49.          *   排序的逻辑 
    50.          *     如果两个数组转换为列表的长度都大于零 
    51.          *     此时比较两个数组的第一个元素  将较小的放在放在集合里 
    52.          *     循环 一次排放 
    53.          *     每一次循环结束条件 必有列表的元素为空 
    54.          *     无论那一个 列表为空 直接放到列表后面就好 原因如下：
    55.          *       - 假设 leftList为空 ，根据判断条件和弹出条件 可以知道  leftList的所有所有元素          *         一定小于 rightList的剩余元素
    56.          *         rightList 和 leftList 都是一个递增的列表
    57.          *       - 所有的数组在上面的递归拆分条件下 最终都以leftList 和 rightList
    58.          *         为单个元素的情况 进行merge 之后 返回的数组一定是递增顺序的 。
    59.          */
    60.         while (leftList.size() >0 && rightList.size() > 0) {
    61.             result.add(
    62.                     leftList.getFirst() < rightList.getFirst() ? leftList.removeFirst() : rightList.removeFirst()
    63.             );
    64.         }
    65.         result.addAll(leftList);
    66.         result.addAll(rightList);
    67.         int[] array = result.stream().flatMapToInt(IntStream::of).toArray();
    68.         System.out.println(Arrays.toString(array));
    69.         return array;
    70.     }
    71. // 输出结果
    72. [1, 3]
    73. [5, 7]
    74. [1, 3, 5, 7]
    75. [3, 8]
    76. [0, 6]
    77. [0, 4, 6]
    78. [0, 3, 4, 6, 8]
    79. [0, 1, 3, 3, 4, 5, 6, 7, 8]
    80. [0, 1, 3, 3, 4, 5, 6, 7, 8]