Arrays.sort()逻辑学习

简单开始

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

        //如果输入数组的长度小于7的话，优先采用插入排序,会对长度小于7的数组进行排序
        //排序完成后返回
        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;
        }

        //递归排序、分成两半来进行排序
        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 (((Comparable)src[mid-1]).compareTo(src[mid]) <= 0) {
            System.arraycopy(src, low, dest, destLow, length);
            return;
        }

        //如果在经过递归排序后，数组的顺序没有被排好，那么使用归并排序合并两个序列
        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++];
        }
    }

补充

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

实际上，我们是通过调用sort方法然后通过sort方法来调用对应的排序方法来完成排序操作的。如果用户请求传统的归并排序，即LegacyMergeSort.userRequested 的值为true，可以通过下面的语句来使用传统归并排序。

System.setProperty("java.util.Arrays.useLegacyMergeSort","true");

接下来我们做一个简单的小Case来走一遍流程，可以看到，在我们没有使用上述语句时，程序调用的是优化后的归并排序。

使用传统归并排序

最后

在下一篇博客里、我们再来深入学习一下归并排序及其优化，然后再结合ComparableTimSort的源代码来探讨下在Java中的使用。