为什么使用Collections.sort的该程序仅对大小为32或更大的列表失败？

Question

以下程序引发以下异常：

java.lang.IllegalArgumentException: Comparison method violates its general contract!

我了解的问题Comparator。请参阅无法复制：“比较方法违反了它的一般约定！”

我不明白为什么它只会List在大小为32或更大的情况下失败。谁能解释？

class Experiment {

    private static final class MyInteger {
        private final Integer num;

        MyInteger(Integer num) {
            this.num = num;
        }
    }

    private static final Comparator<MyInteger> COMPARATOR = (r1, r2) -> {
        if (r1.num == null || r2.num == null)
            return 0;
        return Integer.compare(r1.num, r2.num);
    };

    public static void main(String[] args) {
        MyInteger[] array = {new MyInteger(0), new MyInteger(1), new MyInteger(null)};
        Random random = new Random();
        for (int length = 0;; length++) {
            for (int attempt = 0; attempt < 100000; attempt++) {
                List<MyInteger> list = new ArrayList<>();
                int[] arr = new int[length];
                for (int k = 0; k < length; k++) {
                    int rand = random.nextInt(3);
                    arr[k] = rand;
                    list.add(array[rand]);
                }
                try {
                    Collections.sort(list, COMPARATOR);
                } catch (Exception e) {
                    System.out.println(arr.length + " " + Arrays.toString(arr));
                    return;
                }
            }
        }
    }
}

Answer 1

它取决于实现，但是在openjdk
8
中，将根据MIN_MERGE（等于32）检查数组的大小。这避免了对mergeLo/
的调用，mergeHi后者会引发异常。

从JDK / jdk / openjdk / 7u40-b43 8-b132 7-b147-8-b132 /
java.util.TimSort
：

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;

    int nRemaining  = hi - lo;
    if (nRemaining < 2)
        return;  // Arrays of size 0 and 1 are always sorted

    // If array is small, do a "mini-TimSort" with no merges
    if (nRemaining < MIN_MERGE) {
        int initRunLen = countRunAndMakeAscending(a, lo, hi, c);
        binarySort(a, lo, hi, lo + initRunLen, c);
        return;
    }

    /**
     * March over the array once, left to right, finding natural runs,
     * extending short natural runs to minRun elements, and merging runs
     * to maintain stack invariant.
     */
    TimSort<T> ts = new TimSort<>(a, c, work, workBase, workLen);
    int minRun = minRunLength(nRemaining);
    do {
        // Identify next run
        int runLen = countRunAndMakeAscending(a, lo, hi, c);

        // If run is short, extend to min(minRun, nRemaining)
        if (runLen < minRun) {
            int force = nRemaining <= minRun ? nRemaining : minRun;
            binarySort(a, lo, lo + force, lo + runLen, c);
            runLen = force;
        }

        // Push run onto pending-run stack, and maybe merge
        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;
}