Background:

I'm debugging a Java sorting setup where I found a faulty Comparator already (violates the contract). My goal is to implement a test case which provokes the well-known

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

thrown by TimSort for such Comparators.

How do I provoke the error?
I repeatedly shuffle and sort a list with many "problematic" values (e.g., many elements with the same field value). This is very reliable an reproducable, after a couple runs the expected error is thrown.

for (int i = 0; i < 10_000; i++) {
    List shuffled = new ArrayList<>(input);
    Collections.shuffle(shuffled);
    try {
        List sorted = new ArrayList<>(shuffled);
        Collections.sort(sorted, faultyComparator);
    } catch (Exception e) {
        // Store the list that triggered the exception!
        triggerOrder = new ArrayList<>(shuffled);
        break;
    }
}

My confusion:

After successfully capturing a list (triggerOrder) that caused the contract violation error, I expect replaying the sort with exactly this same order and comparator to yield the same error every time.

But when I switch the input to a found triggerOrder for the next execution the sort runs fine! Even further shuffling of triggerOrder respectively input never provokes the error again.

The input generator:

List input = IntStream
// starting order to find a trigger order
        .of(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40)
// a found trigger order
//        .of(10, 7, 27, 24, 33, 13, 23, 19, 37, 25, 22, 31, 1, 35, 18, 28, 29, 3, 9, 8, 15, 39, 14, 10, 10, 34, 17, 26, 2, 12, 4, 32, 5, 11, 16, 36, 38, 21, 10, 6)
        .mapToObj(i -> new Pojo(null, i % 10 == 0 ? 10 : i, i + ".pdf"))
        .collect(Collectors.toCollection(ArrayList::new));

class Pojo {
    private String name;
    private Integer date;
    private String file;

    public Pojo(String name, int date, String file) {
        this.name = name;
        this.date = date;
        this.file = file;
    }

    // Getter
}

Just if you're curios, the faulty comparator (I know it's rubbish ;)):

Comparator faultyComparator = (b1, b2) -> {
    if (b1 == null && b2 == null) return 0;
    if (b1 == null) return -1;
    if (b2 == null) return 1;
    final int result = compareToNullSave(b1.getName(), (b2.getName()));
    if (result != 0) return result;
    final int dateResult = b1.getDate().compareTo(b2.getDate());
    if (dateResult != 0) return result; // this should be "return dateResult;"
    return compareToNullSave(b1.getFile(), b2.getFile());
}

public static int compareToNullSave(String s1, String s2) {
    if (s1 == null) return s2 == null ? 0 : -1;
    if (s2 == null) return 1;
    return s1.compareTo(s2);
}

My question:

Why does a shuffle-found trigger order, which reliably causes a TimSort comparator contract violation in one run, fail to reproduce the exception in another run?

• The comparator is still broken in the same way.
• The error is provoked in a shuffle-for loop easily.
• Re-playing with the exact list order (that triggered the error) in a new run does not throw. Whereas the trigger order in the same run reliable reproduces the error.
• Even further shuffling doesn't seem to help after that.

Is TimSort doing some kind of internal magic with runs, memory layout or merging that's dependent on more than just the input order?
Is there any way to reliably construct an input order that always triggers the exception?

Explanations/Efficiency:

• Why does the sort outcome seem non-deterministic w.r.t. the input order?
• What should I know about TimSort’s inner mechanics that makes the error appear and disappear like this?

Thanks in advance for any insights!