精选文章｜Arrays.sort的背后jdk干了什么

    public static <T> void sort(T[] a, Comparator<? super T> c) {        if (c == null) {            //没有Comparator，走ComparableTimSort排序逻辑            sort(a, fromIndex, toIndex);        } else {            //越位，范围检查            rangeCheck(a.length, fromIndex, toIndex);            //LegacyMergeSort.userRequested默认返回false            //legacyMergeSort(a, fromIndex, toIndex, c)方法要被时代淘汰了            if (LegacyMergeSort.userRequested)                legacyMergeSort(a, fromIndex, toIndex, c);            else                //主角TimSort排序                TimSort.sort(a, fromIndex, toIndex, c, null, 0, 0);        }    }

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

    /** To be removed in a future release. */    private static <T> void legacyMergeSort(T[] a, int fromIndex, int toIndex,                                            Comparator<? super T> c) {        T[] aux = copyOfRange(a, fromIndex, toIndex);        if (c==null)            mergeSort(aux, a, fromIndex, toIndex, -fromIndex);        else            mergeSort(aux, a, fromIndex, toIndex, -fromIndex, c);    }

/**     * Sorts the given range, using the given workspace array slice     * for temp storage when possible. This method is designed to be     * invoked from public methods (in class Arrays) after performing     * any necessary array bounds checks and expanding parameters into     * the required forms.     *     * @param a the array to be sorted     * @param lo the index of the first element, inclusive, to be sorted     * @param hi the index of the last element, exclusive, to be sorted     * @param c the comparator to use     * @param work a workspace array (slice)     * @param workBase origin of usable space in work array     * @param workLen usable size of work array     * @since 1.8     */    static <T> void sort(T[] a, int lo, int hi, Comparator<? super T> c,                         T[] work, int workBase, int workLen) {        //合法性校验        assert c != null && a != null && lo >= 0 && lo <= hi && hi <= a.length;        //检查数组是否需要排序，元素个数在2以下说明已经具备顺序性        int nRemaining  = hi - lo;        if (nRemaining < 2)            return;          //如果数组个数在32个以下，则不用进行归并排序，使用二分插入排序        //private static final int MIN_MERGE = 32;        if (nRemaining < MIN_MERGE) {            // 找出连续升序的最大个数            int initRunLen = countRunAndMakeAscending(a, lo, hi, c);            // 二分插入排序            binarySort(a, lo, hi, lo + initRunLen, c);            return;        }                //以下是走timsort排序        TimSort<T> ts = new TimSort<>(a, c, work, workBase, workLen);        //计算分区最小个数，少于这个长度就需要对其进行扩展。        int minRun = minRunLength(nRemaining);        do {            // 找出 排序数组中 一段升序数组 的长度            int runLen = countRunAndMakeAscending(a, lo, hi, c);
            //如果归并分区个数小于之前计算出的minRun            if (runLen < minRun) {                int force = nRemaining <= minRun ? nRemaining : minRun;                // 二分插入排序                binarySort(a, lo, lo + force, lo + runLen, c);                runLen = force;            }
            // 归并            ts.pushRun(lo, runLen);            ts.mergeCollapse();
            // Advance to find next run            lo += runLen;            nRemaining -= runLen;        } while (nRemaining != 0);
        // Merge all remaining runs to complete sort        assert lo == hi;        ts.mergeForceCollapse();        assert ts.stackSize == 1;    }

    private static int minRunLength(int n) {        assert n >= 0;        int r = 0;      // Becomes 1 if any 1 bits are shifted off        while (n >= MIN_MERGE) {            r |= (n & 1);            n >>= 1;        }        return n + r;    }

    private static <T> int countRunAndMakeAscending(T[] a, int lo, int hi,                                                    Comparator<? super T> c) {        assert lo < hi;        int runHi = lo + 1;        if (runHi == hi)            return 1;
        // Find end of run, and reverse range if descending        if (c.compare(a[runHi++], a[lo]) < 0) { // Descending            while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) < 0)                runHi++;            reverseRange(a, lo, runHi);        } else {                              // Ascending            while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) >= 0)                runHi++;        }
        return runHi - lo;    }

    @SuppressWarnings("fallthrough")    private static <T> void binarySort(T[] a, int lo, int hi, int start,                                       Comparator<? super T> c) {        assert lo <= start && start <= hi;        if (start == lo)            start++;        //遍历无序的后半端区域[start,hi]        for ( ; start < hi; start++) {            T pivot = a[start];            int left = lo;            int right = start;            assert left <= right;            //二分查找，查找出在[lo,start]区间中 元素满足 a[n]<pivot<a[n+1]            while (left < right) {                int mid = (left + right) >>> 1;                if (c.compare(pivot, a[mid]) < 0)                    right = mid;                else                    left = mid + 1;            }            assert left == right;            //在分区升序情况下 二分查找出 pivot 的位置 left和right             //将 此角标 到 原来pivot角标 的所有元素后移一位              int n = start - left;  // The number of elements to move            // Switch is just an optimization for arraycopy in default case            switch (n) {                case 2:  a[left + 2] = a[left + 1];                case 1:  a[left + 1] = a[left];                         break;                default: System.arraycopy(a, left, a, left + 1, n);            }            a[left] = pivot;        }    }

    /**     * Pushes the specified run onto the pending-run stack.     *     * @param runBase index of the first element in the run     * @param runLen  the number of elements in the run     */    private void pushRun(int runBase, int runLen) {        this.runBase[stackSize] = runBase;        this.runLen[stackSize] = runLen;        stackSize++;    }

    /**     * 将栈顶的两个分区，进行合并，此时每个分区都已经是升序状态     */    private void mergeCollapse() {        while (stackSize > 1) {            int n = stackSize - 2;            //当栈内元素大于3个元素 且第一个分区长度 小于等于 第2个分区长度 加 第3个分区长度            if (n > 0 && runLen[n-1] <= runLen[n] + runLen[n+1]) {                //第一个分区长度 小于 第3个分区长度                if (runLen[n - 1] < runLen[n + 1])                    n--;                mergeAt(n);            //当栈内元素有且只有2个元素 且第一个分区长度 小于等于 第2个分区长度             } else if (runLen[n] <= runLen[n + 1]) {                mergeAt(n);            } else {                break; // Invariant is established            }        }    }
    private void mergeAt(int i) {        assert stackSize >= 2;        assert i >= 0;        assert i == stackSize - 2 || i == stackSize - 3;
        int base1 = runBase[i];        int len1 = runLen[i];        int base2 = runBase[i + 1];        int len2 = runLen[i + 1];        assert len1 > 0 && len2 > 0;        assert base1 + len1 == base2;                //合并分区        runLen[i] = len1 + len2;        //合并后移动栈中元素的位置        if (i == stackSize - 3) {            runBase[i + 1] = runBase[i + 2];            runLen[i + 1] = runLen[i + 2];        }        stackSize--;                //用第2个分区的第一个元素 在 第1个分区 寻找 它的合适位置index        //index之前是有序的，之后就是要归并 第2分区的所有元素 和 第1分区index之后的元素        int k = gallopRight(a[base2], a, base1, len1, 0, c);        assert k >= 0;        base1 += k;        len1 -= k;        if (len1 == 0)            return;
        //与上面同理 找到run1的最后一个元素在run2中的位置。        //随后的元素在run2中可以忽略(因为它们已经就绪)。        len2 = gallopLeft(a[base1 + len1 - 1], a, base2, len2, len2 - 1, c);        assert len2 >= 0;        if (len2 == 0)            return;
        // Merge remaining runs, using tmp array with min(len1, len2) elements        if (len1 <= len2)            mergeLo(base1, len1, base2, len2);        else            mergeHi(base1, len1, base2, len2);    }

        /*         * Allocate runs-to-be-merged stack (which cannot be expanded).  The         * stack length requirements are described in listsort.txt.  The C         * version always uses the same stack length (85), but this was         * measured to be too expensive when sorting "mid-sized" arrays (e.g.,         * 100 elements) in Java.  Therefore, we use smaller (but sufficiently         * large) stack lengths for smaller arrays.  The "magic numbers" in the         * computation below must be changed if MIN_MERGE is decreased.  See         * the MIN_MERGE declaration above for more information.         * The maximum value of 49 allows for an array up to length         * Integer.MAX_VALUE-4, if array is filled by the worst case stack size         * increasing scenario. More explanations are given in section 4 of:         * http://envisage-project.eu/wp-content/uploads/2015/02/sorting.pdf         */        int stackLen = (len <    120  ?  5 :                        len <   1542  ? 10 :                        len < 119151  ? 24 : 49);        runBase = new int[stackLen];        runLen = new int[stackLen];