"Comparison method violates its general contract!" - finding small sample data set

Question

Possible Duplicate:
“Comparison method violates its general contract!”

I have a larger sample of partially sorted data (> 700 items) which I want to sort with Java 7 and get the following exception:

java.lang.IllegalArgumentException: Comparison method violates its general contract!
    at java.util.TimSort.mergeLo(TimSort.java:747)
    at java.util.TimSort.mergeAt(TimSort.java:483)
    at java.util.TimSort.mergeCollapse(TimSort.java:410)
    at java.util.TimSort.sort(TimSort.java:214)
    at java.util.TimSort.sort(TimSort.java:173)
    at java.util.Arrays.sort(Arrays.java:659)
    at java.util.Collections.sort(Collections.java:217)

Now I'm trying to lower the size of the data set to make finding the reason simpler. I've written a small application which picks a random subset out of the larger set to reproduce the exception.

private static final int SUBSET_SIZE = 32;

public void testSorting() {
    ...
    final Random random = new Random();
    for (int i = 10000000; i-- > 0; ) {
        testFew(strings, random);
    }
}

private void testFew(List<String> strings, Random random) {
    final List<String> list = new ArrayList<String>();
    int index = 0;
    for (int i = 0; i < SUBSET_SIZE; i++) {
        final int rnd = random.nextInt(strings.size() / 100) + 1;
        index = (index + rnd) % strings.size();
        list.add(strings.get(index));
    }

    try {
        Collections.sort(list, MY_COMPARATOR);
    }
    catch (RuntimeException ex) {
        for (String s : list) {
            System.err.println(s);
        }
        throw ex;
    }
}

The strange thing is that finding a sample to reproduce is very simple if the subset contains at least 32 items, but I've did not succeeded in finding a smaller set. IMHO, this smells rather like a bug in the sorting algorithm than in our comparator.

I bet $1000 that the bug is in your code, and not in the sort algorithm. Why not post its code for us to inspect it, along with the full stack trace of the exception? — JB Nizet, Nov 04 '12 at 12:50

score 7 · Answer 1 · answered Nov 04 '12 at 12:51

7

This means your Comparator has a bug in such that compareTo(a, b) != -compareTo(b, a)

answered Nov 04 '12 at 12:51

Peter Lawrey

525,659
79
751
1,130

No, this I've already checked. – Mot Nov 04 '12 at 13:38
3

Still willing to bet that's where the bug is. You appear to be unwilling to post the code so we can check. ;) – Peter Lawrey Nov 04 '12 at 13:43

score 5 · Answer 2 · answered Nov 04 '12 at 12:49

IMHO, this smells rather like a bug in the sorting algorithm than in our comparator.

To me, this smells like 2 different sort algorithms being used depending on the size of the input set.

While it is not impossible that there is a bug in the sort implementation, it is far, far more likely that the problem is in your Comparator ... like the exception message is saying. You would be advised to focus your efforts on your code rather looking for (probably non-existent) bugs in the library code.

score 2 · Accepted Answer · answered Nov 04 '12 at 13:01

As Stephen C already guessed, this is the result of two different sorting methods being used.

Look at the code of java.util.TimSort:

static <T> void sort(T[] a, Comparator<? super T> c) {
    sort(a, 0, a.length, c);
}

static <T> void sort(T[] a, int lo, int hi, Comparator<? super T> c) {

    // ...

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

    // ...

The value of MIN_MERGE is indeed 32, and the methods that throw your exception are only called in the other case.

Mot · Answer 4 · 2012-11-04T14:07:44.880

1

The error is in our comparator (it violated A < B && B < C -> A < C), but I assumed, that TimSort will always result in the stacktrace which seems to be wrong.

edited Nov 04 '12 at 14:07

answered Nov 04 '12 at 13:37

Mot

28,248
23
84
121

hi Mot can you please post your complete set, original compartor and the fixed one. Actually the reason for asking this is that I am getting the same err with String in our prod env and I am trying to figure out how its breaking actually. so dont have data – manocha_ak Mar 26 '15 at 14:04
My comparator is pretty simple ------ new Comparator() { public int compare(String str1, String str2) { return str1.substring(3).compareTo(str2.substring(3)); } } --------- May it was the same as yur original still not able to figure out how it breaks transitivity, can you please help – manocha_ak Mar 26 '15 at 14:05

"Comparison method violates its general contract!" - finding small sample data set

4 Answers4