Why does this program using Collections.sort only fail for lists of size 32 or more?

Question

The following program throws the following exception:

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

I understand the problem with the Comparator. See Unable to replicate : "Comparison method violates its general contract!"

I don't understand why it only fails for Lists of size 32 or more. Can anyone explain?

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

It depends on the implementation, but in openjdk 8 the size of the array is checked against MIN_MERGE, which is equal to 32. This avoids the call to mergeLo/mergeHi which throw the exception.

From 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;
}