Confluence throws "Comparison method violates its general contract!" when trying to sort multiple long-running tasks

Code to reproduce

Use a unit test below to reproduce this by running the comparator:

        Collections.sort(fullList, (o1, o2) -> {
            // Sorting by name is not as good as sorting by start time (unavailable) but better than anything
            // else we can think of this iteration. Changing this order later is unable to raise any blockers
            // in production.
            Message o1Name = o1.getName();
            if (o1Name == null || o1Name.getKey() == null)
                return 1;  // push o1 to bottom

            Message o2Name = o2.getName();
            if (o2Name == null || o2Name.getKey() == null)
                return -1;  // push o2 to bottom

            return o1Name.getKey().compareTo(o2Name.getKey());
        });

Which is copied from Confluence code.

Confluence will throw the following error message:

Comparison method violates its general contract!

That basically means that the comparator is not written correctly.

Environments

Attached a test class to reproduce the error: ContractViolationTest.java

• on Windows 10,
• java version "1.8.0_111" Java(TM) SE Runtime Environment (build 1.8.0_111-b14), Java HotSpot(TM) Client VM (build 25.111-b14, mixed mode)
• Important: it only breaks if collection size is >= 32

A possible fix in Confluence

Switching the +1 and -1 return values in the comparator's two if blocks fixes the problem.
Note that this change makes "null key" cases appear before "not-null key" cases in the sorted list. It does not affect the original order of objects where the key is not-null.

Workaround

Adding this JVM system property fixes the issue:
-Djava.util.Arrays.useLegacyMergeSort=true

References

• TimSort has been introduced in Java 7, it is a stable sort that was designed for relatively expensive comparison operations. Only used for sorting objects, not primitives. Its problematic code path is only reached for collections with size >= 32. See http://stackoverflow.com/questions/4018332/is-java-7-using-tim-sort-for-the-method-arrays-sort
• Exception might be caused by non-transitive comparators: http://stackoverflow.com/questions/8327514/comparison-method-violates-its-general-contract
• Atlassian has seen something similar, too: https://confluence.atlassian.com/fishkb/comparison-method-violates-its-general-contract-387941517.html
• Oracle has open issues related to this, promised to be fixed in Java 9: http://bugs.java.com/bugdatabase/view_bug.do?bug_id=7075600
• See: com.atlassian.confluence.api.impl.service.longtasks.LongTaskFactory#buildStatus