Arrays.mergeSort() 解析

Arrays 在对 Object 数组进行排序是会使用到 legacyMergeSort 和 ComparableTimSort.sort

    public static void sort(Object[] a) {
        if (LegacyMergeSort.userRequested)
            legacyMergeSort(a);
        else
            ComparableTimSort.sort(a, 0, a.length, null, 0, 0);
    }

其中 legacyMergeSort 调用的就是 mergeSort 方法

1. legacyMergeSort(Object[] a): 需要配置 java.util.Arrays.useLegacyMergeSort == true, 代码注释说会在以后的发行版本中移除 legacyMergeSort 方法

    /** To be removed in a future release. */
    private static void legacyMergeSort(Object[] a) {
        Object[] aux = a.clone();
        mergeSort(aux, a, 0, a.length, 0);
    }

来看看 mergeSort 的具体实现。

• 当 array.length < 7 时会使用插入排序(insertion sort)

        // Insertion sort on smallest arrays
        if (length < INSERTIONSORT_THRESHOLD) {
            for (int i=low; i<high; i++)
                for (int j=i; j>low &&
                         ((Comparable) dest[j-1]).compareTo(dest[j])>0; j--)
                    swap(dest, j, j-1);
            return;
        }

迭代的时候每次都选择当前 index 后面最大的元素进行交互位置

• 完整的 mergeSort() 实现

 private static void mergeSort(Object[] src,
                                  Object[] dest,
                                  int low,
                                  int high,
                                  int off) {
        int length = high - low;

        // Insertion sort on smallest arrays
        if (length < INSERTIONSORT_THRESHOLD) {
            for (int i=low; i<high; i++)
                for (int j=i; j>low &&
                         ((Comparable) dest[j-1]).compareTo(dest[j])>0; j--)
                    swap(dest, j, j-1);
            return;
        }

        // Recursively sort halves of dest into src
        int destLow  = low;
        int destHigh = high;
        low  += off;
        high += off;
        int mid = (low + high) >>> 1;
        mergeSort(dest, src, low, mid, -off);
        mergeSort(dest, src, mid, high, -off);

        // If list is already sorted, just copy from src to dest.  This is an
        // optimization that results in faster sorts for nearly ordered lists.
        if (((Comparable)src[mid-1]).compareTo(src[mid]) <= 0) {
            System.arraycopy(src, low, dest, destLow, length);
            return;
        }

        // Merge sorted halves (now in src) into dest
        for(int i = destLow, p = low, q = mid; i < destHigh; i++) {
            if (q >= high || p < mid && ((Comparable)src[p]).compareTo(src[q])<=0)
                dest[i] = src[p++];
            else
                dest[i] = src[q++];
        }
    }

以一个 length 为 16 的数组举例,大致解释一下 mergeSort 排序:
调用 mergeSort 方法时 length 为 16, 因为 length 为 8 不满足插入排序的条件， 此时将数组分为两半:
数组1的 index 范围为: [0, 8)
数组2的 index 范围为: [8, 16)
继续看数组1: 对数组以递归调用, 因为 length 为 8 不满足插入排序的条件，此时将数组1分为 2 半:
数组1_1, index 范围为: [0, 4)
此时满足 length < 7 的条件, 进行插入排序
数组1_2, index 范围为: [4, 8)
此时也满足 length < 7 的条件, 进行插入排序
此时 数组1_1 和 数组1_2 都是局部有序的, 然后下一步会判断 数组1_1 的最大值与 数组1_2 的最小值之间的关系, 如果 max(数组1_1) <= min(数组1_2) 则说明 数组1_1 + 数组1_2 也是有序的的,
否则对 数组1_1 和 数组1_2 进行2-路归并排序，最终得到的结果是 数组 index 为[0, 8) 的数据都是有序的

对数组2 进行两次递归调用后，数组 index 为[8, 16) 的数据都是有序的，判断数组1 的最大值和数组2 的最小值之间的关系, 如果 max(数组1) <= min(数组2)，则说明 数组1 + 数组2 也是有序的的,
否则对 数组1 和 数组2 进行 2-路归并排序得到最终结果

以上就是 mergeSort 排序的全部过程了