先使每个子序列有序，再使子序列段间有序。 平均时间复杂度： 代码如下：
/** * 归并排序 * * @param arr */ public static int[] mergeSort(int[] arr) { if (arr == null) { return null; } return mergeSort(arr, 0, arr.length); } public static int[] mergeSort(int[] arr, int begin, int end) { // 当子数组的元素个数多于 2个时，将其拆分，直到其元素个数小于2个 if (end - begin > 2) { // 将数组对半拆分(递归) int[] resultA = mergeSort(arr, begin, begin + (end - begin) / 2); int[] resultB = mergeSort(arr, begin + (end - begin) / 2, end); return mergeArr(resultA, resultB); } else if (end - begin == 1) { // 当子数组的元素个数为1个时，直接返回 return Arrays.copyOfRange(arr, begin, end); } else if (arr[begin] < arr[begin + 1]) { // 当子数组中后面的元素大于前面的元素时，返回该子数组 return new int[]{arr[begin], arr[begin + 1]}; } else { // 当子数组中后面的元素小于前面的元素时，交换两个数的位置 然后返回该子数组 return new int[]{arr[begin + 1], arr[begin]}; } } /** * 将两个有序数组合并 * * @param * @return */ public static int[] mergeArr(int[] arr1, int[] arr2) { if (arr1 == null) { return arr2; } if (arr2 == null) { return arr1; } // arr1 的索引 int p1 = 0; // arr2 的索引 int p2 = 0; // 新数组的索引 int pr = 0; int[] res = new int[arr1.length + arr2.length]; while (p1 < arr1.length || p2 < arr2.length) { // 当 arr2 耗尽了 或者 arr1 小于 arr2 时，将 arr1 放到新数组中，其余的将 arr2 放到新数组中 if (p2 >= arr2.length || p1 < arr1.length && arr1[p1] <= arr2[p2]) { res[pr] = arr1[p1]; p1++; } else { res[pr] = arr2[p2]; p2++; } pr++; } return res; }